kmp模闆

很多詳細解析也看了，隻能說學稍微複雜點的東西需要老老實實yy，急沒有鳥用###

代碼對應洛谷的闆子；

--

#include<bits/stdc++.h>
using namespace std;
char ls[1000009],lt[1000009];
int pre[1000009],ans[1000009];
int main()
{

    freopen("lys.in","r",stdin);

    cin>>(lt+1);
    cin>>(ls+1);


    int k=0;
    pre[1]=0;


    for(int i=2;i<=strlen(ls+1);i++)
    {
        while(k&&ls[i]!=ls[k+1]) k=pre[k];

        if(ls[i]==ls[k+1]) k++;

        pre[i]=k;
    }

    int num=0;
    k=0;
    for(int j=1;j<=strlen(lt+1);j++)
    {
        while(k&&lt[j]!=ls[k+1]) k=pre[k];
        if(lt[j]==ls[k+1]) k++;
        if(k==strlen(ls+1))
        {
            num++;
            ans[num]=j-strlen(ls+1)+1;
        }
    }


    for(int i=1;i<=num;i++)
    {
        cout<<ans[i]<<endl;
    }
    for(int i=1;i<=strlen(ls+1);i++) cout<<pre[i]<<" ";
}