Description
T(T<=10)组数据，每组|S|<=1e5
Solution
-
考虑翻转操作，这个问题的实质就是很多个回文串嵌套在一起，再补上一些零散的位置。
-
对于回文串以及回文字串的问题，回文树（回文自动机）就能够很好地解决。
-
那么考虑翻转的两个性质（这里不给出证明）：
(1) S与rev(S)的组成代价是一样的。
(2) 如果一个回文串是偶数长度，那么必然又它的一半翻转得到。 -
我们可以在回文树上面DP
-
设设 fa[x]为回文串节点 x 的父亲，fail[x]为回文串 x 的最长前缀回文串
(不包括自己)，half[x]为回文串 x 的最长的满足长度不超过 x 的一半的前缀回文串
- 如果当前串x长度是奇数：
(1)可以从fa[x]两边各加一个字符
(2)也可以是fail[x]补上一连串。
仔细想一想，这样是可以涵盖所有的组合方案的。
f [ x ] = min ( f [ fa [ i ] ] + 2 ,f [ fail [ i ] ]+len[ i ]-len[ fail[ i ] ]) - 如果当前串x长度是偶数：
(1)必然由一半得过来。所以可以是fa[x]在翻转前补一位才翻转，这样得到。
(2)或者由截一半的里面的某个部分补成一半，再翻转，这种情况不好处理，不妨变为先从前缀转移，再通过(1)转移得到。所以这个前缀不能超过一半。
f [ x ]=min ( f [ fa[ i ] ] + 1,f [ half[ i ] ] + len[ i ] / 2 - len[ half [ i ] ] + 1)
P.S.关于half的求法，可以构出fail树，然后half[x]一定是x的树上祖先，又因为len单调递增，所以可以用一个指针顶住half的位置。用人工栈遍历即可。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;
int T,n,i,j,k,ans;
int p,last,cur,now,c;
int fail[maxn],next[maxn][26],s[maxn],len[maxn],fa[maxn];
int em,e[maxn],nx[maxn],ls[maxn],half[maxn],f[maxn];
char ch;
int newnode(int l){
memset(next[p],0,sizeof(next[p]));
len[p]=l;
return p++;
}
void predo(){
memset(ls,0,sizeof(ls));
p=0; newnode(0); newnode(-1);
em=n=last=0; s[n]='*'; fail[0]=1;
}
int get_fail(int x){
while (s[n-len[x]-1]!=s[n]) x=fail[x];
return x;
}
void insert(int x,int y){
em++; e[em]=y; nx[em]=ls[x]; ls[x]=em;
}
int t,w,d[maxn],I[maxn],vis[maxn];
void bfs(){
for(i=0;i<p;i++) I[i]=ls[i];
t=w=1; d[1]=1;
while (w){
int x=d[w];
if (I[x]){
int y=e[I[x]];
while (t<w&&len[d[t+1]]*2<=len[y]) t++;
half[y]=d[t];
d[++w]=y;
I[x]=nx[I[x]];
} else{
w--;
while (len[d[t]]*2>len[d[w]]) t--;
}
}
}
int main(){
freopen("ceshi.in","r",stdin);
scanf("%d",&T);
while (T--){
ch=getchar(); while (ch<'a'||ch>'z') ch=getchar();
predo();
n=0;
while (ch>='a'&&ch<='z'){
c=ch-'a';
s[++n]=c;
cur=get_fail(last);
if (!next[cur][c]){
now=newnode(len[cur]+2);
fail[now]=next[get_fail(fail[cur])][c];
fa[now]=cur;
next[cur][c]=now;
}
last=next[cur][c];
ch=getchar();
}
for(i=0;i<p;i++) if (i!=1) insert(fail[i],i);
bfs();
memset(f,0,sizeof(f));
f[0]=1,f[1]=0,ans=n;
for(i=2;i<p;i++) {
if (len[i]&1)
f[i]=min(f[fa[i]]+2,f[fail[i]]+len[i]-len[fail[i]]);
else
f[i]=min(f[fa[i]]+1,f[half[i]]+len[i]/2-len[half[i]]+1);
ans=min(ans,n-len[i]+f[i]);
}
printf("%d
",ans);
}
}