回文自动机

 1 //bzoj4044
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 int q,_len,son[100010][4],len[100001],f[100001],fail[100001],pre[100001],num[100001],st[100001],tot,n,last,ans;
 9 char s[100001];
10 int u(char ch){
11     return ch=='A'?0:ch=='T'?1:ch=='C'?2:3;
12 }
13 int newnode(int l){
14     for(int i=0;i<4;i++)son[tot][i]=0;
15     len[tot]=l;
16     return tot++;
17 }
18 void init(){
19     tot=n=last=0;
20     newnode(0);
21     newnode(-1);
22     fail[0]=1;
23     st[0]=-1;
24 }
25 int get_fail(int u){
26     while(st[n-len[u]-1]!=st[n])u=fail[u];
27     return u;
28 }
29 void ins(int c){
30     st[++n]=c;
31     int now=get_fail(last);
32     if(!son[now][c]){
33         int newn=newnode(len[now]+2);
34         fail[newn]=son[get_fail(fail[now])][c];
35         if(len[newn]<=2)pre[newn]=fail[newn];
36         else{
37             int v=pre[now];
38             while(st[n-len[v]-1]!=st[n]||(len[v]+2)*2>len[newn])v=fail[v];
39             pre[newn]=son[v][c];
40         }
41         son[now][c]=newn;
42     }
43     last=son[now][c];
44 }
45 void dp(){
46     int u,v;
47     queue<int>q;
48     for(int i=2;i<tot;i++){
49         if(len[i]%2==1)f[i]=len[i];
50     }
51     q.push(0);
52     f[0]=1;
53     while(!q.empty()){
54         u=q.front();
55         q.pop();
56         for(int i=0;i<4;i++){
57             if(son[u][i]){
58                 v=son[u][i];
59                 f[v]=min(f[u]+1,len[v]/2-len[pre[v]]+f[pre[v]]+1);
60                 ans=min(ans,_len-len[v]+f[v]);
61                 q.push(v);
62             }
63         }
64     }
65 }
66 int main(){
67     scanf("%d",&q);
68     while(q--){
69         scanf("%s",s);
70         init();
71         ans=_len=strlen(s);
72         for(int i=0;i<_len;i++){
73             ins(u(s[i]));
74         }
75         dp();
76         printf("%d
",ans);
77     }
78     return 0;
79 }