KMP

给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 P 在模式串 S 中多次作为子串出现。
求出模板串 P 在模式串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。
数据范围
1≤N≤105
1≤M≤106
输入样例：

3
aba
5
ababa

输出样例：

0 2

算法思想：

相较于暴力算法，利用已经匹配好的部分子串的信息，不回退模板串，而只回退模式串。
当然回退多少需要next数组来帮助，含义是非平凡(不是原串自身)最长公共前后缀的长度

时间复杂度 O(m + n)
空间复杂度 O(n)

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] sss) throws IOException{
        // Scanner sc = new Scanner(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        String p = br.readLine();
        int m = Integer.parseInt(br.readLine());
        String s = br.readLine();
        int[] ne = new int[n];
        //模式串与模式串匹配求ne。 本质是dp
        //定义k-max(str)为字符串str中前缀与后缀相同的最大长度。
        //      例如 str = "abcab", k-max(str) = 2
        //定义sub(str, n) 为字符串str从0开始， 到n结束的子串，左闭右开[0, n)，即子串长度为n
        //所以有 k-max(sub(str, n))表示str的从0开始的长度为n的子串的最长相同前后缀。
        //ne[i] = k-max(sub(str, i+1))
        //也就是说ne是这样一个数组，数组中的每个元素存储了模式串对应位置的子串的最长前后缀。
        //ne[0] = k-max(sub(str, 1))
        //ne[1] = k-max(sub(str, 2))
        //i 指向模板串， j 指向模式串 (相对来说！！)
        //而且i和j都指向待比较字符
        //模式串在运行过程中就相当于是前缀，而模板串就是后缀、
        //注意初始化i=1，不能写成i=0，否则会导致ne[0] = 1，从而导致一连串错误
        for (int i = 1, j = 0; i < n; i++) {
            //如果当前位置不匹配，j只能回退到能匹配到的最近位置
            //while的两个结束条件：
            //1. 最坏情况，j == 0, 退到开头（第一个字符）， 退无可退。
            //2. 当前待比较字符不同
            while (j > 0 && p.charAt(i) != p.charAt(j)) j = ne[j - 1];
            //这个if语句的含义是：
            //判断上面的while因何种原因退出
            //1. 因j > 0 不满足而退出说明此时j == 0，用if判断最长前后缀是1还是0
            //2. 因去p[i] != q[j]退出说明此时p[i]==p[j]，if结果为真
            if (p.charAt(i) == p.charAt(j)) j++;
            //更新当前子串最长前后缀
            ne[i] = j;
            // 小小的优化
            // 在匹配第i+1个字符时如果不匹配，需要找ne[i]继续匹配
            // 如果p[i+1]==p[ne[i]]，下一次仍不匹配，需要找ne[ne[i]]继续匹配
            if (i + 1 < m && p.charAt(i + 1) == p.charAt(j))
                ne[i] = ne[j];
        }
        //正式进行字符串匹配
        for (int i = 0, j = 0; i < m; i++) {
            while (j > 0 && s.charAt(i) != p.charAt(j)) j = ne[j - 1];
            if (s.charAt(i) == p.charAt(j)) j++;
            if (j == n) {
                j = ne[j - 1];
                  bw.write(i - n + 1 + " ");
            }
        }
        br.close();
        bw.close();   
    }   
}

更多例题：

参考：
如何更好地理解和掌握 KMP 算法?
y总的参考代码以及下面的评论代码