基本写法

import java.io.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 100010;
    static int M = 1000010;
    static char[] P = new char[N];
    static char[] S = new char[M];
    static int[] next = new int[N];

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        P = br.readLine().toCharArray();
        int m = Integer.parseInt(br.readLine());
        S = br.readLine().toCharArray();

        buildNextArray(n);

        matchPattern(m, n);
        out.flush();
    }

    static void buildNextArray(int n) {
        for (int i = 1, j = 0; i < n; i++) {
            while (j > 0 && P[i] != P[j]) j = next[j - 1];
            if (P[i] == P[j]) j++;
            next[i] = j;
        }
    }

    static void matchPattern(int m, int n) {
        int i = 0, j = 0;
        while (i < m) {
            while (j > 0 && S[i] != P[j]) j = next[j - 1];
            if (S[i] == P[j]) j++;
            if (j == n) {
                out.print(i - j + 1 + " ");
                j = next[j - 1];
            }
            i++;
        }
    }
}

理解

进行真前缀和真后缀的匹配问题next数组记录当前字符串的最长匹配，根据该特性我们可以构造一个前缀字符串，也就是匹配串，其长度为n，再增添一个字符(保证唯一即可)，继续拼接模板串，根据next[i]的值为n那么就可以知道在我们新的字符串中长度为n的前缀和长度为n的后缀相同，又因为我们构造的字符串的前缀就是匹配串，这样就找到了一个字符串，输出索引即可i - 2 * n(输出的是在模板串中的索引)

import java.io.*;

public class Main {
    static final int N = 1100010;
    static int[] next = new int[N];
    static StringBuilder str = new StringBuilder();
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        n = Integer.parseInt(br.readLine());
        str.append(br.readLine()).append("*");
        m = Integer.parseInt(br.readLine());
        str.append(br.readLine());

        buildNext();

        for (int i = n; i <= n + m; i++) {
            if (next[i] == n) {
                out.print(i - 2 * n + " ");
            }
        }
        out.flush();
    }

    static void buildNext() {
        next[0] = 0;
        for (int i = 1; i < str.length(); i++) {
            int j = next[i - 1];
            while (j > 0 && str.charAt(i) != str.charAt(j))
                j = next[j - 1];
            if (str.charAt(i) == str.charAt(j)) j++;
            next[i] = j;
        }
    }
}

应用

找周期

公式：n - next[n - 1]
也就是长度减去整体字符串的next值
说明：
对于任意一个字符串###???###(#表示已知字符串，?表示未知字符串可以任意)选取长度n - next[n - 1]也就是选择了###???那么对于复制串为###???###???###就可以覆盖，不难发现少一个不行

import java.util.*;

public class Main {
    static final int N = 1000010;
    static int[] next = new int[N];
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        if (n == 0) return;
        String str = sc.next();
        {
            next[0] = 0;
            for (int i = 1; i < n; i++) {
                int j = next[i - 1];
                while (j > 0 && str.charAt(i) != str.charAt(j))
                    j = next[j - 1];
                if (str.charAt(i) == str.charAt(j)) j++;
                next[i] = j;
            }
            int ans = n - next[n - 1];
            System.out.println(ans);
        }
    }
}