java代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 100010;     // 模板串的数据规模
    static final int M = 1000010;    // 匹配字符串的数据规模
    static char[] p = new char[N];  // 模板串
    static char[] s = new char[M];  // 被匹配字符串
    static int[] next = new int[N]; // next数组
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 对输入数据进行初始化
        int n = sc.nextInt(); // 模板串的长度
        String p1 = sc.next();
        for (int i = 1; i <= n; i++) p[i] = p1.charAt(i - 1);
        int m = sc.nextInt(); // 被匹配字符串的长度
        String s1 = sc.next();
        for (int i = 1; i <= m; i++) s[i] = s1.charAt(i - 1);

        // 求 next的过程
        for (int i = 2, j = 0; i <= n; i++) {   // i = 1的时候只有一个元素, 最长前缀的长度为 0
            while (j != 0 && p[i] != p[j + 1]) j = next[j];
            if (p[i] == p[j + 1]) j++;
            next[i] = j;
        }

        // kmp匹配过程
        // i指向 s将要匹配的位置, j指向已经匹配模板串已经匹配成功的位置
        for (int i = 1, j = 0; i <= m; i++) {
            while (j != 0 && s[i] != p[j + 1]) j = next[j];  // 进行 next跳转
            // 继续进行匹配, 如果此时模板串的字符和被匹配字符串的字符相等, 继续向下进行匹配++
            if (s[i] == p[j + 1]) j++;
            // 如果匹配成功
            if (j == n) {
                out.print(i - n + " "); // 将 s串中起点的位置写入
                j = next[j];    // 进行 next跳转
            }
        }
        out.flush();
    }
}