BZOJ 2565: 最長雙回文串（回文樹）

看懂題意，看懂題意，看懂題意

開始沒看懂題意，WA到崩潰

題目給一個字元串S，要你求最長的T

T：S的子串，并且T是兩個回文串的拼接

BZOJ上樣例的解釋：

S=baacaabbacabb

從S的第二個字元開始到S的最後一個字元結束的子串 T=aacaabbacabb

T可分為aacaa與bbacabb兩部分，且兩者都是回文串，并且這也是滿足條件的最長的T。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define max(a,b) a>b?a:b
const int maxn=100000+100;

int tree[maxn][26],len[maxn],fail[maxn],tot,suff;
int Maxlen[maxn][2];
char ch[maxn];

inline void insert(int pos){
    
    int ind=ch[pos]-'a';
    int cur=suff;
    int curlen=len[suff];
    
    while(true){
        
        int locate=pos-1-curlen;
        if(locate>=0 && ch[locate]==ch[pos]) break;
        cur=fail[cur];
        curlen=len[cur];
    }
    
    if(tree[cur][ind]){
        
        suff=tree[cur][ind];
        return;
    }
    
    tree[cur][ind]=++tot;
    len[tot]=len[cur]+2;
    suff=tot;

    if(cur==0){
        
        fail[tot]=1;
        return;
    }
    
    while(true){
        
        cur=fail[cur];
        curlen=len[cur];
        int locate=pos-1-curlen;
        if(locate>=0 && ch[locate]==ch[pos]){
            
            fail[tot]=tree[cur][ind];
            break;
        }
    }
}

void init(){
    
    tot=suff=1;
    memset(tree,0,sizeof(tree));
    len[0]=-1,len[1]=0;
    fail[0]=0,fail[1]=0;
}

int main(){
    
    init();
    scanf("%s",ch);
    int n=strlen(ch);
    for(int i=0;i<n;i++) insert(i),Maxlen[i][0]=len[suff];
    init();
    for(int i=0;i<n/2;i++) swap(ch[i],ch[n-i-1]);
    for(int i=0;i<n;i++) insert(i),Maxlen[n-i-1][1]=len[suff];
    int Max=0;
    for(int i=0;i<n-1;i++) Max=max(Max,Maxlen[i][0]+Maxlen[i+1][1]);
    printf("%d\n",Max);
}