NaiveMartin's Blog

namespace kmp{
    const int AL=1000000,BL=1000000;
    char a[AL+10],b[BL+10];
    int pr[BL+10],al,bl;
    void build(){
        for(int i=2,j=0;i<=bl;++i){
            while(j>0&&b[j+1]!=b[i])j=pr[j];
            if(b[j+1]==b[i])++j;
            pr[i]=j;
        }
    }
    int run(){
        int r=0;
        for(int i=1,j=0;i<=al;++i){
            while(j>0&&a[i]!=b[j+1])j=pr[j];
            if(a[i]==b[j+1])++j;
            if(j==bl)++r,j=pr[j];
        }
        return r;
    }
}