前述：

之前写过扩展kmp的题，但记忆不太深刻又忘记了，自己的模板上也没解释，那么这里就写一下吧，弥补之前的懒惰。

初学者不建议看。

自我对扩展KMP的理解：     

        自我觉得扩展KMP与mannacher算法都差不多，都是利用之前已经计算过的地方，去获取一个已经计算过的长度，然后再暴力计算未计算的长度。而kmp与扩展kmp有很大的不同

EXkmp:s[i...k+i-1]与s[0...k-1]相等的最大的k  (普通kmp是以i为后缀的相同的最长前缀,而扩展kmp是i为前缀的最长前缀)


例题

洛谷例题：P5410 【模板】扩展 KMP

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
char a[maxn],b[maxn];
int exb[maxn],exkmp[maxn];
/*
EXkmp:s[i...k+i-1]与s[0...k-1]相等的最大的k  (普通kmp是以i为后缀的相同的最长前缀,而扩展kmp是i为前缀的最长前缀)
exb[i]:b[i...k+i-1]与b[0...k-1]相等的最大的k
exkmp[i]:a[i..k+i-1]与b[0..k-1]相同的最大的k
*/
void pre_kmp(char s[],int ls,int next[])//预处理字符串b的kmp
{
    int id,maxr;//最长扩展的i和延申的位置maxr
    next[0]=ls;
    id=-1,maxr=-1;
    for(int i=1;i<ls;++i)
    {
        int qs;//next[i]的值
        if(maxr-i+1<=0)//不在可以扩展的范围,那就自己先为0
            qs=0;
        else
            qs=min(maxr-i+1,next[i-id]);//可扩展,取min以防出边界
        while(i+qs<ls&&s[i+qs]==s[qs]) ++qs;//暴力扩展未知的
        next[i]=qs;
        if(qs+i-1>maxr){
            maxr=qs+i-1;
            id=i;
        }
    }
}
void EXkmp(char a[],int la,char b[],int lb,int next[],int exkmp[])
{
    pre_kmp(b,lb,next);
    int id=-1,maxr=-1;
    for(int i=0;i<la;++i){
        int qs;
        if(maxr-i+1<=0) qs=0;
        else qs=min(maxr-i+1,next[i-id]);
        while(i+qs<la && qs<lb && a[i+qs]==b[qs]) ++qs;
        exkmp[i]=qs;
        if(qs+i-1>maxr){
            maxr=qs+i-1;
            id=i;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>a>>b;
    int lb=strlen(b);
    int la=strlen(a);
    EXkmp(a,la,b,lb,exb,exkmp);
//    pre_kmp(b,lb,exb);
    for(int i=0;i<lb;++i)
        cout<<exb[i]<<" ";
    cout<<endl;
    for(int i=0;i<la;++i)
        cout<<exkmp[i]<<" ";
    cout<<endl;
    return 0;
}

hdu 6629：string matching

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
char s[maxn];
ll exs[maxn];
void pre_kmp(char s[],ll ls,ll next[])//预处理字符串b的kmp
{
    ll id,maxr;//最长扩展的i和延申的位置maxr
    next[0]=ls;
    id=-1,maxr=-1;
    for(ll i=1; i<ls; ++i)
    {
        ll qs;//next[i]的值
        if(maxr-i+1<=0)//不在可以重用数据的范围
            qs=0;
        else
            qs=min(maxr-i+1,next[i-id]);//可扩展,取min以防出边界
        while(i+qs<ls&&s[i+qs]==s[qs]) ++qs;
        next[i]=qs;
        if(qs+i-1>maxr)
        {
            maxr=qs+i-1;
            id=i;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>s;
        ll ans=0;
        ll ls=strlen(s);
        pre_kmp(s,ls,exs);
        for(ll i=1; i<ls; ++i)
        {
            if(i+exs[i]==ls)
                ans+=exs[i];
            else
                ans+=exs[i]+1;
        }
        cout<<ans<<endl;
    }

    return 0;
}