kmp

模板

#include<iostream>
#include<cstring>

using namespace std;

char s[1000001],p[1000001];
int pmt[1000001];
void get_pmt(int len){
    int j=0;
    for(int i=1;i<len;i++){
        while(j&&p[i]!=p[j]) j=pmt[j-1];
        if(p[i]==p[j]) j++;
        pmt[i]=j;
    }
}
void match(int slen,int plen){
    int j=0;
    for(int i=0;i<slen;i++){
        while(j&&s[i]!=p[j]) j=pmt[j-1];
        if(s[i]==p[j]) j++;
        if(j==plen){
            cout<<i-plen+2<<"\n";
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>s>>p;
    int slen=strlen(s),plen=strlen(p);
    get_pmt(plen);
    match(slen,plen);
    for(int i=0;i<plen;i++){
        cout<<pmt[i]<<" ";
    }
}

原理

PMT(partial match table)

对于每一个 pmt(i)， 实际上记录的是字符串前缀和后缀相等的最长长度
那这东西有啥用呢？实际上是为了方便我们在字符串失配时做回溯处理
假设用朴素算法来求解字符串匹配问题，我们会怎么做？
当然是用两个指针分别指向待寻找串和模式串

reference

https://zhuanlan.zhihu.com/p/105629613