题目描述

（kmp用于匹配字符串）
主要思想：
现在有两个字符串s[] p[],s[]为匹配串，p[]为模板串，我们需要在s[]中找到p[]串。

当我们用暴力做法时，我们会定义 i 和 j 两个指针分别指向s,p 用一个双重循环疯狂匹配，时间复杂度是很恐怖的。

kmp算法定义了一个ne[] ne[]数组会告诉我们以下信息，当s[j+1]！=p[i]时按照暴力做法模板串会像右边移动一格，
然后j从1开始继续匹配，现在如果有人告诉你p[]中j——ne[j]已经与s[i]之前的匹配成功，我们只需要继续判断s[i]是否与
p[j+1]相等，如果相等j，i继续匹配，否则继续递归的找ne[i],当j=0的时候意思是当s[i]之前的都无法与p[j]匹配
所以i++，j=0，继续试图匹配。

样例

3
aba
5
ababa

算法1

(KMP)

时间复杂度

O（n+m）

C++ 代码

#include<iostream>

using namespace std;

int const N=1e5+10,M=1e6+10;
int n,m,ne[N];
char p[N],s[M];

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

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

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