【CERC2014】bzoj4044 Virus synthesis

虽然最终的串不一定是回文串，但是它一定是先生成某个回文串再把剩下的字符加上得到的。因此我们只需要计算每个回文串最少需要几次得到。
如果一个回文串长度为奇数，生成的最后一步一定是添加字符，唯一的生成方法是先生成$fail$再填上剩下的字符。如果是偶数的话，除了上面那种方法，最后一步还可以是翻折。这样也有两种，一种是$SxxS$，一种是$xSSx$，其中$S$表示已有的字符串，$x$表示新添加的字符。后一种比较好处理，用每个回文串都向它的$trans$指针更新。前一种用每个回文串的$fail$节点中最长的长度不超过它的一半的节点$next$更新。这些都可以按照$val$从小到大的拓扑序更新一遍得到。
需要注意$next$的求法，暴力求$next$复杂度会达到$O(n^2)$，但是考虑到一个节点的$fail$节点的$next$一定不会比它的$next$长，我们可以按照上述拓扑序的逆序计算更新$next$。
这样最后的复杂度是$O(n)$。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=400010,oo=0x3f3f3f3f;
/*void pause() {int x;x=0; }*/
int id(char c)
{switch (c){case 'A':return 1;break;case 'G':return 2;break;case 'C':return 3;break;case 'T':return 4;break;}
}
char s[maxn];
int a[maxn],trans[maxn][10],fail[maxn],val[maxn],
f[maxn],cnt[maxn],que[maxn],next[maxn];
void solve()
{int p,np,q,ans=oo,n,tot=1,last=1;scanf("%s",s+1);n=strlen(s+1);for (int i=1;i<=n;i++) a[i]=id(s[i]);for (int i=1;i<=4;i++) trans[0][i]=trans[1][i]=0;fail[0]=fail[1]=1;val[1]=-1;p=1;for (int i=1;i<=n;i++){p=last;while (a[i-val[p]-1]!=a[i]) p=fail[p];if (!trans[p][a[i]]){np=++tot;for (int j=1;j<=4;j++) trans[np][j]=0;val[np]=val[p]+2;q=fail[p];while (a[i-val[q]-1]!=a[i]) q=fail[q];fail[np]=trans[q][a[i]];trans[p][a[i]]=np;next[np]=fail[np];}last=trans[p][a[i]];}for (int i=0;i<=tot;i++) f[i]=val[i];for (int i=0;i<=n;i++) cnt[i]=0;for (int i=2;i<=tot;i++) cnt[val[i]]++;for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1];for (int i=2;i<=tot;i++) que[cnt[val[i]]--]=i;/*for (int i=0;i<=tot;i++){printf("%d:",i);for (int j=1;j<=4;j++) printf("%d ",trans[i][j]);putchar('\n');}*/for (int i=tot-1;i;i--){while (val[next[que[i]]]*2>val[que[i]]) next[que[i]]=fail[next[que[i]]];if (val[next[que[i]]]<val[next[fail[que[i]]]]) next[fail[que[i]]]=next[que[i]];}for (int i=1;i<tot;i++){//if (i==23) pause();//if (que[i]==23) pause();//if (que[i]==4) pause();f[que[i]]=min(f[que[i]],f[fail[que[i]]]+val[que[i]]-val[fail[que[i]]]);if (!(val[que[i]]&1)){f[que[i]]=min(f[que[i]],f[next[que[i]]]+val[que[i]]/2-val[next[que[i]]]+1);for (int j=1;j<=4;j++)f[trans[que[i]][j]]=min(f[trans[que[i]][j]],f[que[i]]+1);}//if (i==23) pause();ans=min(ans,n-val[que[i]]+f[que[i]]);}printf("%d\n",ans);
}
int main()
{//freopen("in.txt","r",stdin);int T;scanf("%d",&T);while (T--) solve();
}