题目描述

KMP，记下笔记，以后再补充了。

样例

3
aba
5
ababa

直接上图

C++ 代码

#include<iostream>
using namespace std;

const int N = 1e5+10;
const int M = 1e6+10;

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

int main()
{
    int n,m;
    scanf("%d",&n);
    getchar();//可以直接用cin否则要丢弃换行符
    for(int i=0;i<n;i++) scanf("%c",p+i);

    scanf("%d",&m);
    getchar();
    for(int i=0;i<m;i++) scanf("%c",s+i);

    ne[0] = -1;//表示第一个字符不匹配时，j=-1，之后认为匹配（通配），j++,i++ 主、子串移动一位
    ne[1] = 0;//单字符前后缀为0，注意j=1是第二个字符失配，求以 前一个字符为端点的前后缀
    for(int i=2;i<=n;i++)
    {
        //求第n+1个失配时前后缀是因为：当匹配成功后主串和子串都位于下一个位置，即：j=n，这时第n+1个字符认为失配
        int j = ne[i-1];//一开始用p[i-1] 与 p[ne[i-1]比较
        while(j > -1 && p[i-1] != p[j]) j = ne[j];//j=-1,通配
        j++;
        ne[i] = j;
    }
    int i=0,j=0;
    while(i<m)
    {
        while(j>-1 && s[i] != p[j]) j = ne[j];
        i++,j++;

        if(j == n)//match
        {
            cout << i - n << ' ';
            j = ne[j];//j=n，这时第n+1个字符认为失配，移动子串
        }
    }

    return 0;
}