BZOJ4044 [Cerc2014] Virus synthesis

嗯……备战CCPC?合肥你好

显然只能尽可能地构造一个回文串，其他的就往里面加是了
搞出来PAM，dp[i]为构建长为i的串的最小步数
对于奇数串dp[i]=len[i]
否则dp[i]=min(dp[fa[i]]+1,len[i]/2-len[half[i]]+dp[half[i]]+1)
即究竟是在上一个串末尾添加一个字符翻转
还是由一个串前面加点东西翻过来
half表示i的不超过len[i]/2的最长回文后缀
half的维护在某种意义上暴力就好了

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
char s[maxn];
namespace PAM{
	int tot,last,str[maxn],nxt[maxn][4],n;
	int len[maxn],suf[maxn],cnt[maxn];
	
	int half[maxn],dp[maxn];
	
	int newnode(int l){
		len[tot]=l;
		suf[tot]=0;
		cnt[tot]=0;
		half[tot]=0;
		dp[tot]=0;
		memset(nxt[tot],0,sizeof nxt[tot]);
		return tot++;
	}
	void init(){
		tot=0;n=0;last=0;
		newnode(0);// tree0 is node 0
		newnode(-1);// tree-1 is node 1
		str[0]=-1;
		suf[0]=1;
	}
	int find(int x){
		while(str[n-len[x]-1]!=str[n])x=suf[x];
		return x;
	}
	void add(int c){
		str[++n]=c;
		int u=find(last);
		if(!nxt[u]){
			int v=newnode(len[u]+2);
			suf[v]=nxt[find(suf[u])];
			
			if(len[v]<=2)
				half[v]=suf[v];
			else{
				int x=half[u];
				while(str[n-len[x]-1]!=str[n] || (len[x]+2)*2>len[v])x=suf[x];
				half[v]=nxt[x];
			}
			
			nxt[u]=v;
		}last=nxt[u];
		cnt[last]++;
	}
	void count(){
		for(int i=tot-1;i>=0;i--)cnt[suf[i]]+=cnt[i];
	}
};
using namespace PAM;
int main(){
	
	freopen("bzoj4044.in","r",stdin);
	
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);
		int n=strlen(s+1);
		init();
		for(int i=1;i<=n;i++){
			int x;
			if(s[i]=='A')x=0;
			if(s[i]=='T')x=1;
			if(s[i]=='C')x=2;
			if(s[i]=='G')x=3;
			add(x);
		}
			
		
		queue<int>q;
		q.push(1);
		q.push(0);
		
		dp[0]=1;
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=0;i<4;i++){
				if(nxt[u][i]){
					int v=nxt[u][i];
				//	cout<< u <<"->" << v <<endl;
					if(len[v]%2==1){
						dp[v]=len[v];
					}else{
						dp[v]=min(dp[u]+1,len[v]/2-len[half[v]]+dp[half[v]]+1);
					}
					q.push(v);
				}
			}	
		}
		//for(int i=2;i<tot;i++)
		//	printf("%d\tsuf=%d\thalf=%d\tdp=%d\n",i,suf[i],half[i],dp[i]);
		int ans=n;
		for(int i=2;i<tot;i++)
			ans=min(ans,n-len[i]+dp[i]);
		printf("%d\n",ans);
	}
	return 0;
}