[CERC2014] Virus synthesis

設f[i]為形成極長迴文串i的最小操作數。答案為min f[i]+n-len[i]。
在不形成偶迴文的情況下形成奇迴文的最小操作數為該串長度。可以不考慮（但ans賦為len）。

正確性基於：
1）奇、偶迴文嵌套形成最終的偶迴文一定可以轉化為由在不形成奇迴文的情況下形成偶迴文。
2）奇、偶迴文嵌套形成最終的奇迴文並不需要討論。

也不知道理解對沒有。。。

所以，以下的迴文串皆代指偶迴文。

轉移1：f[i]=f[j]+1 | 在極長迴文串j前後補上一對相同字元可得到i。
舉例：
aabbaa : a aa aab aabbaa
caabbaac: a aa aab caab caabbaac
統一化：f[偶根]=1 => f["aa"]=2

轉移2：f[i]=min f[j]+1+len[i]/2-len[j] | j=tmp[i].
舉例：
abba : a ab abba
abbaccabba: abba abbac abbaccabba

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;

map<char,int> tr={
    {'A',0},{'G',1},{'C',2},{'T',3}
};

struct pam_ {
    char *str;
    int last,size;
    int tmp[N],len[N],fail[N],ch[N][26];
    int getFail(int x,int n) {
        while(str[n]!=str[n-len[x]-1]) x=fail[x];
        return x;
    }
    void build(char *bStr) {
        str=bStr;
        str[0]=-1;
        len[1]=-1;
        fail[0]=1;
        last=0;
        size=1;
        memset(ch[0],0,sizeof ch[0]);
        memset(ch[1],0,sizeof ch[1]);
        for(int i=1; str[i]; ++i) {
            int c=tr[str[i]];
            int p=getFail(last,i);
            if(!ch[p][c]) {
                int q=++size;
                memset(ch[q],0,sizeof ch[q]);
                len[q]=len[p]+2;
                fail[q]=ch[getFail(fail[p],i)][c]; 
                ch[p][c]=q;
                if(len[q]<=2) tmp[q]=fail[q];
                else {
                    int x=tmp[p];
                    while(str[i]!=str[i-len[x]-1]||(len[x]+2)*2>len[q]) x=fail[x];
                    tmp[q]=ch[x][c];
                }
            }
            last=ch[p][c];
        }
    }
    int calc() {
        static int que[N];
        static int f[N];
        int n,ans,hd,tl;
        n=ans=strlen(str+1);
        que[hd=0,tl=1]=0;
        for(int i=2; i<=size; ++i) {
            f[i]=len[i];
        }
        f[0]=1,f[1]=0;
        while(hd<tl) {
            int x=que[++hd];
            for(int i=0; i<4; ++i) {
                int y=ch[x][i];
                if(!y) continue;
                f[y]=f[x]+1;
                que[++tl]=y;
                f[y]=min(f[y],f[tmp[y]]+1+len[y]/2-len[tmp[y]]);
                ans=min(ans,f[y]+n-len[y]);
            }
        }
        return ans;
    }
} pam;

int main() {
    int T;
    scanf("%d",&T);
    static char str[N];
    while(T--) {
        scanf("%s",str+1);
        pam.build(str);
        // puts("built");
        printf("%d\n",pam.calc());
    }
    return 0;
}