Gym - 101981M：（南京） Mediocre String Problem（回文树+exkmp）

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

char S[maxn],T[maxn];

struct PT

{

    struct in{

        int dep,fail,len,son[];

    }p[maxn];

    int cnt,last;

    void init()

    {

        //memset(p,0,sizeof(p));

        cnt=last=;p[].dep=p[].dep=;

        p[].fail=p[].fail=;

        p[].len=; p[].len=-;

    }

    int add(int c,int n)

    {

        int np=last;

        while(S[n]!=S[n--p[np].len]) np=p[np].fail;

        if(!p[np].son[c]){

            int v=++cnt,k=p[np].fail; p[v].len=p[np].len+;

            while(S[n]!=S[n-p[k].len-]) k=p[k].fail;

            p[v].fail=p[k].son[c];

            p[np].son[c]=v; //这一句放前面会出现矛盾，因为np可能=k

            p[v].dep=p[p[v].fail].dep+;

        }

        last=p[np].son[c];

        return p[last].dep;

    }

}Tree;

int N,M,num[maxn],Next[maxn],extand[maxn]; ll ans;

void getnext(){// next[i]: 以第i位置开始的子串与T的公共前缀长度

     int i,length=strlen(T+);

     Next[]=length;

     for(i=;i+<length&&T[i+]==T[i+];i++);

     Next[]=i;

     int a=;   //!

     for(int k=;k<=length;k++){//长度+1，位置-1。

          int p=a+Next[a]-, L=Next[k-a+];

          if(L>=p-k+){

              int j=(p-k+)>?(p-k+):;//中断后可能是负的

              while(k+j<=length&&T[k+j]==T[j+]) j++;// 枚举(p+1，length) 与(p-k+1,length) 区间比较

              Next[k]=j, a=k;

          }

          else Next[k]=L;

    }

}

void getextand(){

    memset(Next,,sizeof(Next));

    getnext();

    int Slen=strlen(S+),Tlen=strlen(T+),a=;

    int MinLen=Slen>Tlen?Tlen:Slen;

    while(a<MinLen&&S[a+]==T[a+]) a++;

    extand[]=a; a=;

    for(int k=;k<=Slen;k++){

        int p=a+extand[a]-,L=Next[k-a+];

        if(L>=p-k+){

            int j=(p-k+)>?(p-k+):;

            while(k+j<=Slen&&j+<=Tlen&&S[k+j]==T[j+]) j++;

            extand[k]=j;a=k;

        }

        else extand[k]=L;

    }

}

int main()

{

    scanf("%s%s",S+,T+);

    N=strlen(S+); M=strlen(T+);

    reverse(S+,S+N+); Tree.init();

    rep(i,,N) num[i]=Tree.add(S[i]-'a',i);

    getextand();

    rep(i,,N) ans+=(ll)num[i-]*extand[i];

    printf("%lld\n",ans);

    return ;

}

不知道写什么。。。