831. 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

推荐一个非常好的视频，适合0基础，或者看了好几遍视频还是不理解的

「天勤公开课」KMP算法易懂版

求next数组的过程

移动指针到第一个不匹配的字符


1.仔细观察会发现，箭头左边的字符串，上下模式串和主串是完全匹配的，如图

2.模式串左右两端有两个字串，是完全匹配的，这两个字串称为模式串的公共前后缀

根据这两点，我们可以这么做
直接往前移动模式串，使得其公共前后缀里的前缀直接移动到了原先的后缀所在的位置(KMP的核心)，这样移动可以保证，当前比较指针所在的位置它左边的串上下的匹配的(因为公共前后缀是匹配的，移动之前指针左边的串上下是匹配的)

所以我们现在只需要求模式串中的最长公共前后缀就可以了，也就是说，如果模式串中有多对前后缀，我们要取最长的那一对

比较指针继续往后扫描，扫描到下面位置又不匹配了，然后找最长公共前后缀

移动模式串，使得模式串中前缀与后缀重合，这时候发现模式串已经超出主串范围了，就可以判断匹配失败，主串中不含有和模式串中相同的字符

所以我们在做这些操作的时候根本不需要看主串

结论

每次开始比较的位置编号，其值就等于最大公共前后缀长度+1

具体代码

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String p = "1" + in.next();
        int m = in.nextInt();
        String s = "1" + in.next();
        int next[] = new int[n + 1];

        //求next[]的过程
        for (int i = 2, j = 0; i <= n; i++) {//因为next[1]=0,所有i从2开始
            while (j > 0 && p.charAt(i) != p.charAt(j + 1))//不匹配
                j = next[j];
            if (p.charAt(i) == p.charAt(j + 1)) {//匹配成功
                j++;

            }
            next[i] = j;
        }

        //KMP匹配的过程
        for (int i = 1, j = 0; i <= m; i++) {//i是枚举的当前的i,j和当前s[i]匹配的是p[j+1],因此j是总往前错1位
            while (j > 0 && s.charAt(i) != p.charAt(j + 1))//j没有退回起点(j退回起点的含义是要重新匹配了),并且当前的s[i],不能和p[j+1]匹配
                j = next[j];
            if (s.charAt(i) == p.charAt(j + 1))//已经匹配
                j++;
            if (j == n) {//匹配成功
                out.print((i - n) + " ");
                j = next[j];//匹配成功再往后退一步
            }
        }
        out.flush();
    }
}