N1786 - 찾기

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.util.List;
import java.util.ArrayList;


public class Main {
    static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
    static String text;
    static String pattern;

    public static void main(String[] args) throws IOException {
        List<Integer> arr;
        getInput();

        arr = solution();
        BW.write(arr.size()+ "\n");

        for(int i : arr)
            BW.write(i+"\n");

        BW.close();
        BW.close();
    }

    static void getInput() throws IOException {
        text = BR.readLine();
        pattern = BR.readLine();
    }

    static List<Integer> solution() {
        List<Integer> arr = new ArrayList<>();
        int[] pi = getPi(pattern);
        int idx = 0;
        int tlen = text.length();
        int plen = pattern.length();

        for (int i = 0; i < tlen; i++) {
            while (idx > 0 && text.charAt(i) != pattern.charAt(idx))
                idx = pi[idx-1];

            if (pattern.charAt(idx) == text.charAt(i)) {
                if (idx == plen-1) {
                    arr.add(i-idx+1);
                    idx = pi[idx];
                } else {
                    idx++;
                }
            }
        }

        return arr;
    }

    static int[] getPi(String pattern) {
       int[] pi = new int[pattern.length()];
       int tmp = pattern.length();
       int idx = 0;

       for (int i = 1; i < tmp; i++) {
           while (idx > 0 && pattern.charAt(idx) != pattern.charAt(i))
               idx = pi[idx-1];

           if (pattern.charAt(idx) == pattern.charAt(i))
               pi[i] = ++idx;
       }
       return pi;
    }

}