题目描述

给定一个模式串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

算法1

KMP算法思想 $O(n)$

核心就是建立next数组，使用i遍历模式串，使用j记录i之前的字符子串中最长前缀的下标，不包括i；
即next[i]为[1,…,i-1]这个区间的最长前缀的下标。
所以每次对p[j+1]与p[i]进行比较，因为p[1,…,j]==p[i-j,…,i-1],不用在比较;

比如，模式串p：aabaac，
当i=5,则一开始j=1；
先判断p[i]==p[j+1]
如果等于，则j=j+1;next[i]=j，这里是j=2,next[5]=2;即求得p[1-5]之间最长前缀下标为2
如果不等于，则根据最长前缀进行回溯直到相等或者退无可退为止。

匹配过程：
1、先判断j==0,如果等于，则退无可退，跳出循环；

如果不等，则判断p[j+1]==s[i]，

如果相等，则跳出循环，如果不等，回溯。
2、跳出循环后，要判断是因为哪个条件才跳出的。
如果因为退无可退，那么仍然没有前缀，不用j=j+1;
如果因为p[j+1]==s[i]，则最长前缀下标j=j+1;

C++ 代码

#include <iostream>

using namespace std;
const int N=100010,M=1000010;

int n,m;
char p[N],s[M];
int ne[N];

int main(){
    cin>>n;
    cin>>p+1;
    cin>> m;
    cin>>s+1;

    int i,j;
    ne[1]=0;
    for (i = 2,j=0; i <= n; ++i) {
        while (j!=0 && p[j+1]!=p[i]) j=ne[j];
        if (p[i]==p[j+1]) j++;
        ne[i]=j;
    }

    for(i=1,j=0;i<=m;i++){
        while(j!=0 && p[j+1]!=s[i]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==n) {
            cout<<i-n<<" ";
            j=ne[j];
        }
    }


}