设f[x]表示得到x这个回文串的最小步数，则ans=min(n-len[x]+f[x])

边界条件f[长度为0的偶回文串]=1

因为翻转只会得到偶回文串，所以f[奇回文串]=该串的长度

对于一个偶回文串x，设y为x去掉首尾得到的串，有f[x]=f[y]+1

设y为长度不超过x的一半的x的最长回文后缀，有f[x]=len[x]/2-len[y]+f[y]+1

两种情况取个最小值即可。

对于状态的表示以及最长回文后缀的询问，用回文树支持操作即可。时间复杂度$O(n)$。

 

#include
     
      #include
      
       const int N=100010,S=4;int T,n,i,x,y,ans,all,son[N][S],fail[N],trans[N],f[N],len[N],text[N],last,tot,q[N],h,t;char s[N];inline int newnode(int l){  for(int i=0;i
       
        len[y])z=fail[z];      trans[y]=son[z][w];    }    son[x][w]=y;  }  last=son[x][w];}inline int hash(char c){  if(c=='A')return 0;  if(c=='T')return 1;  if(c=='C')return 2;  return 3;}inline void up(int&a,int b){if(a>b)a=b;}int main(){  for(scanf("%d",&T);T--;printf("%d\n",ans)){    scanf("%s",s+1),ans=n=std::strlen(s+1);    for(init(),i=1;i<=n;i++)add(hash(s[i]));    for(i=2;i