题目描述：
你要用ATGC四个字母用两种操作拼出给定的串：
1.将其中一个字符放在已有串开头或者结尾
2.将已有串复制，然后reverse，再接在已有串的头部或者尾部
一开始已有串为空。求最少操作次数。
len<=100000
题解：
PAM+dp。
先建出PAM，然后对于每一个偶树上的串，满足：
1.得到上一个串时一定是先延长后倍增，所以dp[ i ] = dp[ las ] + 1;
2.先得到一个长<=len/2的串然后延长+倍增，所以dp[ i ] = dp[ pre ] + len/2 - len0 + 1;
代码：
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100050 int T,n; char s[N]; struct pnt { int pre,len,trs[4]; void clear() { pre=len=trs[0]=trs[1]=trs[2]=trs[3]=0; } }p[N]; int ci(char c) { if(c=='A')return 0; if(c=='G')return 1; if(c=='C')return 2; return 3; } int dp[N],ans; struct PAM { int tot,las; void res() { p[0].clear(),p[1].clear(); tot=las=1; p[0].pre=p[1].pre=1; p[1].len=-1; memset(dp,0x3f,sizeof(dp)); } bool mis(int i,int x) { return s[i]!=s[i-p[x].len-1]; } void insert(int i) { int lp = las; while(mis(i,lp))lp=p[lp].pre; int c = ci(s[i]); if(!p[lp].trs[c]) { int np = ++tot; p[np].clear(); int tmp = p[lp].pre; while(mis(i,tmp))tmp=p[tmp].pre; p[np].pre=p[tmp].trs[c]; p[np].len=p[lp].len+2; p[lp].trs[c]=np; } las=p[lp].trs[c]; } int fa[N][21]; void init() { for(int i=0;i<=tot;i++)fa[i][0]=p[i].pre; for(int i=1;i<=20;i++) for(int j=0;j<=tot;j++) fa[j][i]=fa[fa[j][i-1]][i-1]; } int get_mid(int u) { int ret = u; for(int i=20;i>=0;i--) if(p[fa[ret][i]].len*2>=p[u].len)ret=fa[ret][i]; while(p[ret].len&1||p[ret].len*2>p[u].len)ret=p[ret].pre; return ret; } void DP() { dp[0]=0; queue<int>q; for(int i=0;i<4;i++) if(p[0].trs[i]) { dp[p[0].trs[i]]=2; q.push(p[0].trs[i]); } ans = n; while(!q.empty()) { int u = q.front(); q.pop(); int mid = get_mid(u); dp[u]=min(dp[u],dp[mid]+p[u].len/2-p[mid].len+1); ans=min(ans,dp[u]+n-p[u].len); for(int i=0;i<4;i++) if(p[u].trs[i]) { dp[p[u].trs[i]]=dp[u]+1; q.push(p[u].trs[i]); } } } }pam; int main() { scanf("%d",&T); while(T--) { scanf("%s",s+1); n = strlen(s+1); pam.res(); for(int i=1;i<=n;i++) pam.insert(i); pam.init(); pam.DP(); printf("%d ",ans); } return 0; }