KMP
判断p在s中出现的下标
朴素方法

KMP的核心思想是求出以p中第一个与s不同的下标为终点的后缀与p的前缀相同的最大长度l，则same_length(p)-l就是需要移动的最大长度。

ne[i]数组的含义，以i为终点的后缀与以1为起点的前缀相等的最大值

• 例如：ne[i] = j;则p[1 ~ j] = p[i - j + 1 ~ i];

演示：

java算法

import java.io.*;

public class Main {
    static final int N = 100010, M = 1000010;
    static char[] p = new char[N];
    static char[] s = new char[M];
    static int[] ne = new int[M];
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(reader.readLine());
        char[] tmp = reader.readLine().toCharArray();
        System.arraycopy(tmp, 0, p, 1, n);
        m = Integer.parseInt(reader.readLine());
        tmp = reader.readLine().toCharArray();
        System.arraycopy(tmp, 0, s, 1, m);


        // 求ne[i], 因为ne[0] 和 ne[1] == 0，所以直接从2开始
        for (int i = 2, j = 0; i <= n; i++) {
            while (j > 0 && p[i] != p[j + 1]) j = ne[j];  // 如果不能匹配，则将p向前移动
            if (p[i] == p[j + 1]) j++;
            ne[i] = j;
        }

        for (int i = 1, j = 0; i <= m; i++) {
            while (j > 0 && s[i] != p[j + 1]) j = ne[j];
            if (s[i] == p[j + 1]) j++;
            if (n == j) {  // 匹配成功
                writer.write(i - n + " ");
                j = ne[j];
            }
        }

        writer.newLine();
        writer.flush();
        writer.close();
        reader.close();
    }
}