原文链接https://www.cnblogs.com/zhouzhendong/p/CF-100543G.html
题目传送门 - CF-Gym100543G
题意
你可以对一个字符串进行以下两种操作：
1. 在其头或者尾部加入一个新字符
2. 翻转当前字符串，并把他拼接在当前字符串的前面或者后面
给你 T 组询问，每组询问一个字符串，问你至少要多少次操作才能生成这个串。
字符集 = ${'A','C','G','T'}$ ，字符串串长 $leq 100000$
题解
第一次写回文自动机。现学现用。
写完调不出样例。网上看了看 Claris 的代码。研究了一下，继续调。样例是过了，一交 wa 。思索之后，重新打开 Claris 的博客。然后把代码改的和他差不多了 QAQ
做法：
我们先建一棵 PAM 。
然后考虑在 PAM 上面 DP 。
令当前串在 PAM 上面的状态为 $x$ 。
考虑长度为 偶数 的回文串，分两种情况：
折半，令节点 $y$ 为长度小于等于 $len_x$ 的一般的最长回文子串，则 $ dp_x=min(dp_x,dp_y+(cfrac {len_x}{2} - len_y) + 1) $
删除两侧字符，令节点 $y$ 为当前回文串删除两侧节点得到，那么由于我们可以先折半再删除，所以 $dp_x=min(dp_x,dp_y+1)$ 。
考虑长度为 奇数 的回文串，令 $dp_i=len_i$，分两种情况说明他是对的：
该串下一步暴力填充至完成全串： 则选择该串不如直接选择偶串，故令 $dp_i=len_i$ 不亏。
该串由偶串折半而来，那么由于在折半前有偶串的“删除两侧字符”这个转移，故不需要在奇串的转移中加入删除左侧或者右侧字符的转移 。
具体做法见代码。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
struct PAM{
static const int C=4;
int Next[N][C],fail[N],len[N],s[N],last,n,p;
int Half[N];
int newnode(int L){
memset(Next[p],0,sizeof Next[p]);
len[p]=L;
return p++;
}
void init(){
p=last=n=Half[0]=Half[1]=0;
newnode(0),newnode(-1);
s[0]=-1,fail[0]=1,fail[1]=0;
}
int getfail(int x){
while (s[n-len[x]-1]!=s[n])
x=fail[x];
return x;
}
void add(int c){
s[++n]=c;
int x=getfail(last);
if (!Next[x][c]){
int y=newnode(len[x]+2);
fail[y]=Next[getfail(fail[x])][c];
if (len[y]<=2)
Half[y]=fail[y];
else {
int z=Half[x];
while (s[n-len[z]-1]!=s[n]||(len[z]+2)*2>len[y])
z=fail[z];
Half[y]=Next[z][c];
}
Next[x][c]=y;
}
last=Next[x][c];
}
}pam;
int T,n,Turn[300],dp[N];
int q[N],head,tail;
char s[N];
int main(){
Turn['A']=0,Turn['C']=1,Turn['G']=2,Turn['T']=3;
scanf("%d",&T);
while (T--){
scanf("%s",s);
n=strlen(s);
pam.init();
for (int i=0;i<n;i++)
pam.add(Turn[s[i]]);
// 考虑长度为 偶数 的串，分两种情况：
// 折半
// 删除两侧字符
// 考虑长度为 奇数 的串，分两种情况：
// 该串下一步暴力填充至完成全串： 则选择该串不如直接选择偶串，故令 dp[i]=len[i]
// 该串由偶串折半而来，那么由于在折半前有偶串的“删除两侧字符”这个转移，故不需要在奇串的转移中加入删除左侧或者右侧字符的转移
for (int i=2;i<pam.p;i++)
if (pam.len[i]&1)
dp[i]=pam.len[i];
int ans=n;
head=tail=0,dp[0]=1,q[++tail]=0;
while (head<tail)
for (int x=q[++head],i=0;i<4;i++){
int y=pam.Next[x][i];
if (!y)
continue;
dp[y]=min(dp[x]+1,pam.len[y]/2-pam.len[pam.Half[y]]+dp[pam.Half[y]]+1);
ans=min(ans,n-pam.len[y]+dp[y]);
q[++tail]=y;
}
printf("%d
",ans);
}
return 0;
}