KMP算法

1. next[i] = j的含义是： 字符串中的[1, j] 和 [i - j + 1, i]是相等的，并且长度最大。

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
char s[N], p[N];
int n, m;
int ne[N];
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    for(int i = 2, j = 0; i <= n; i ++)
    {
        while(j && p[i] != p[j + 1])j = ne[j];
        if(p[i] == p[j + 1])j ++;
        ne[i] = j;//ne[1] = 0
    }
    
    for(int i = 1, j = 0; i <= m; i ++)
    {
        while(j && s[i] != p[j + 1])j = ne[j];
        if(s[i] == p[j + 1])j ++;
        if(j == n)
        {
            printf("%d ", i - n);//输出从零开始的s字符串中和p字符串相等的子字符串的下标。
            j = ne[j];
        }
    }
}

时间复杂度O(2m)