KMP && manacher

kmp

template<class T>
void get_next(T a[],int lena,T b[],int lenb,int nex[],int res[])
{
    if(a==b)nex[1]=1;
    for(int i=(a==b?2:1),j=1;i<=lena;++i)
        for(res[i]=1;;j=nex[j-1])
            if(a[i]==b[j]){res[i]=++j;break;}
            else if(j==1)break;
}

template<class T>
int kmp(T ys[],int lenys,T pp[],int lenpp,int nex[])
{
    int ans=0;
    for(int i=1,j=1;i<=lenys;++i)
        for(;;j=nex[j-1])
            if(ys[i]==pp[j])
            {
                if(j++==lenpp)//[i-lenpp+1,i]匹配
                    pf("%d\n",i-lenpp+1);
                break;
            }
            else if(j==1)break;
    return ans;
}

exkmp:

template<class T>
//res[i]: a[i…n]与b[1…m]的LCP (已知b串exkmp的nex)
void exkmp(T a[],int lena,T b[],int lenb,int nex[],int res[])
{
    int wz=1,maxx=0;
    for(int i=1;a[i]==b[i] && i<=min(lena,lenb);++i)
        maxx=i;
    res[1]=maxx;
    if(!maxx)maxx=1;
    for(int i=2;i<=lena;++i)
        if(i+nex[i-wz+1]-1>=maxx)
        {
            res[i]=maxx-i+1;
            while(i+res[i]<=lena && res[i]+1<=lenb
                  && a[i+res[i]]==b[res[i]+1])
                ++res[i];
            maxx=max(i+res[i]-1,i);
            wz=i;
        }
        else res[i]=nex[i-wz+1];
}

exkmp(b+1,lenb-1,b,lenb,nex,nex+1);
exkmp(a,lena,b,lenb,nex,ext);

manacher

template<class T>
int manacher(T s[],int len,int pr[])
{
    int n=len<<1|1,res=1;
    for(int i=n,j=len;i>=1;--i)
        if(i&1)s[i]='#';
        else s[i]=s[j--];
    s[n+1]=0,pr[1]=1;
    int wz=1,maxx=1;
    for(int i=2;i<=n;res=max(res,pr[i++]))
        if(i<=maxx && i+pr[2*wz-i]-1!=maxx)
            pr[i]=min(pr[2*wz-i],maxx-i+1);
        else
        {
            pr[i]=max(maxx-i+1,1);
            while(pr[i]+1<=min(n-i+1,i)
                  && s[i+pr[i]]==s[i-pr[i]])
            ++pr[i];
            maxx=i+pr[i]-1,wz=i;
        }
    return res-1;
}

KMP自动机

struct KMPAutomaton
{
    static const int __=1e4+5;
    static const int alp=26;

    static int to_idx(char ch)
    {
        return ch-'A'+1;
    }

    int nex[__][alp+1],n;

#define fail(x) nex[x][0]

    void build(char s[],int len)
    {
        n=len;
        mem(nex[0],0);
        for(int i=0;i<n;++i)
        {
            int k=to_idx(s[i+1]);
            nex[i][k]=i+1;
            if(i)fail(i+1)=nex[fail(i)][k];
            for(int j=1;j<=alp;++j)
                if(j!=k)nex[i][j]=nex[fail(i)][j];
        }
        for(int i=1;i<=alp;++i)
            nex[n][i]=nex[fail(n)][i];
    }

    int KMP(char s[],int len)
    {
        int x=0,ans=0;
        for(int i=1;i<=len;++i)
        {
            x=nex[x][to_idx(s[i])];
            ans+=(x==n);
        }
        return ans;
    }
}K;