KMP

今夜爆肝
md三蹦子还没开始肝

KMP是我一直不想学的东西，这个算法是基于匹配串的特殊性质才能实现的，所以之前有很多地方难以理解。前段时间在秦皇岛又对KMP复习了一下，发现有些地方想通了，今天多校又碰到了一个字符串，自闭之余，还是要接着补题。

Next函数是基于匹配串求出的，Next[ i ]表示“a中以i为结尾的非前缀字串”与“a的前缀”能够匹配的最大长度。

后面的Next可以由前面的Next快速求出，匹配也是同样的思路，直接感性认知吧。。。

int Next[N];
void cacl_Next(char *a){
    Next[1]=0;int n=strlen(a+1);
    for(int i=2,j=0;i<=n;i++){
        while(j>0&&a[i]!=a[j+1])j=Next[j];
        if(a[i]==a[j+1])j++;
        Next[i]=j;
    }
}
int f[N];
int kmp(char *a,char *b){
    cacl_Next(a);int lena=strlen(a+1);
    int ans=0,lenb=strlen(b+1);
    for(int i=1,j=0;i<=lenb;i++){
        while(j>0&&(j==lenb||b[i]!=a[j+1]))j=Next[j];
        if(b[i]==a[j+1])j++;
        f[i]=j;if(f[i]==lena)ans++;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    char a[N],b[N];
    cin>>(a+1);
    cin>>(b+1);
    cout<<kmp(a,b)<<endl;
}

EXKMP

但是杭电这个问题需要用exkmp来解决。exkmp的功能是计算s串的每一个后缀与t串的最长公共前缀，用到的两个数组Next和extend，他们的求解思路都是一样的，extend是s串与t串的答案，Next是t串与自身匹配的答案，此题只需要算出Next数组就可以了。

这个算法对我来说比较抽象，内容已经基本理解了，但是还是感觉理解不够透彻，所以把我看的博客放在下面，以便加深理解。

链接

HDU-6629

int Next[N];
void cacl_exNext(char *T){
    int len=strlen(T+1),pos=2,p=1;
    while(p+1<=len&&T[p]==T[p+1])p++;
    Next[1]=len,Next[2]=p-1;
    for(int i=3;i<=len;i++){
        int l=Next[i-pos+1];
        if(l<p-i+1)Next[i]=l;
        else{
            int j=max(p-i+1,0);
            while(i+j<=len&&T[j+1]==T[i+j])j++;
            p=i+j-1,Next[i]=j,pos=i;
        }
    }
}
int extend[N];
void exKMP(char *S,char *T){
    int lenS=strlen(S+1),lenT=strlen(T+1),p=1,pos;
    while(p<=lenT&&S[p]==T[p])p++;
    extend[1]=--p,pos=1;
    for(int i=2;i<=lenS;i++){
        int l=Next[i-pos+1];
        if(l<p-i+1)extend[i]=l;
        else {
            int j=max(p-i+1,0);
            while(i+j<=lenS&&j<=lenT&&T[j+1]==S[i+j])j++;
            p=i+j-1,extend[i]=j,pos=i;
        }
    }
}
char a[N]; 
int main(){
    ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t--){
        memset(a,0,sizeof(a));
        cin>>(a+1);
        cacl_exNext(a);
        int n=strlen(a+1);
        ll ans=0;
        for(int i=2;i<=n;i++){
            ans+=min(Next[i]+1,n-i+1);
        }
        cout<<ans<<endl;
    }
}