KMP

 字符串匹配[作业部落]

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rg register
using namespace std;
char A[1000001],B[1000001];
int F[1000001];
inline int read()
{
    rg int save=0,w=1;rg char q=getchar();
    while(q<'0'||q>'9'){if(q=='-')w=-1;q=getchar();}
    while(q>='0'&&q<='9')save=(save<<3)+(save<<1)+q-'0',q=getchar();
    return save*w;
}

int main()
{
    scanf("%s%s",A,B);//问B在A中的出现情况
    rg int i,j,lA=strlen(A),lB=strlen(B);
    F[0]=-1;//最长前缀 和 最长后缀 是不能等于总长的!!!
    for(i=1;i<lB;++i)
    {
        j=F[i-1];
        while(j>=0&B[i]!=B[j+1])j=F[j];//若F[j+1]的下一个不能匹配B[i],说明F[i]不能继承自F[j]
        if(B[j+1]==B[i])F[i]=j+1;
        else F[i]=-1;
    }
    i=j=0;
    while(i<lA)
    {
        //当前A[i],B[j]尚未匹配
        if(A[i]==B[j])
        {
            i++,j++;//跳到下一个
            if(j==lB)//若B[]已匹配完
                printf("%d
",i-lB+1),j=F[lB-1]+1;
        }
        else
        {
            if(!j)i++;//假如j处在B[]开头,说明A[i]不能与B[]匹配了
            j=F[j-1]+1;
        }
    }
    for(i=0;i<lB;++i)
        printf("%d ",F[i]+1);
    return 0;
}