自动搬运

查看原文

来自洛谷，原作者为

	Zxc200611 End.

搬运于2025-08-24 22:03:21，当前版本为作者最后更新于2022-03-23 16:28:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Virus synthesis

首先，最后的串一定是一个最后一次翻转得到的回文串在首尾加上一些字符得到的，所以我们最多只能利用原串中的一个回文串。

对原串建出回文自动机。设 $s_u$ 为点 $u$ 所代表的串，$dp_u$ 表示构造 $s_u$ 的最小操作次数，那么答案就是 $\min_u |S|-len_u+dp_u$。

引理 1：如果要得到一个长度为偶数的回文串 $A$，那么最后一次操作肯定是翻转。

证明：$|A|=2$ 时，显然先填一个字符然后翻转不劣。

如果 $|X| \in [2,l]$ 时构造 $X$ 的最后一步都是翻转，$|A|=|X|+1$：

如果最后一次操作不是翻转，找到最后一次翻转出来的回文串 $B$ 所在的位置（如没有翻转操作，那么 $|B|=0$）。设 $|A|=2a,|B|=2b$，构造 $B$ 的一半需要操作 $d$ 次。

• 如果翻转前 $B$ 的一半全部位于 $A$ 回文中心的一边：

  

  绿色是 $B$ 的一半（右边的是翻转前所在的位置）。如果我们用第一种方法，翻转绿色部分得到 $B$，再在两边填黄色的字符，操作数为 $d+1+(2a-2b)$。但如果我们用第二种方法，先在绿色部分两边填上黄色字符，再通过一次翻转得到蓝色部分，那么操作数只有 $d+(a-b)+1$。显然 $a \ge b$，那么第一种方法不优。

• 如果翻转前 $B$ 的一半跨过了 $A$ 的回文中心：

  串中的粗竖线表示回文中心。

  设一个串 $X$ 的反串为 $T(x)$，那么有 $T(F)=D=T(C)=G=T(H)=E$。那么两个串如上，其中黄色和蓝色互为反串、红色和绿色互为反串，设蓝色和黄色长度均为 $L_1$，构造出一段蓝色需要 $d$ 步，红色和绿色长度均为 $L_2$。

  如果按照原来的思路，构造出 $GC$ 后翻转得到 $DH$，添字符得到 $EF$ 与红绿部分，那么需要 $d+1+2L_1+2L_2$ 步。

  $|B|<|A|$，那么构造 $B$ 的最后一步是翻转，那么把翻转前的串 $GC$ 放入 $EF$ 的位置，添字符得到红色部分和 $G$ 再翻转得到 $A$，那么需要 $d+L_1+L_2+1$ 步，显然 $L_1,L_2 \ge 0$，那么总不劣。

引理 2：长度为奇数的回文串对于答案没有影响。

证明：长度为奇数的回文串 $A$ 不能由翻转得到，那么找到构造它的过程中最后一次翻转操作翻转出的串 $B$（如果没有翻转操作那么 $|B|=0$）。$A$ 的转移全部可以视为由 $B$ 转移得到。

下面只考虑偶回文串。

考虑计算 $dp_u$。

• $s_u$ 可以由 $u$ 的父亲 $f$ 代表的串在最后一次翻转操作前在前面添上一个字符再翻转得到，那么有 $dp_u \overset{\min}{\longleftarrow} dp_f+1$。
• $s_u$ 还可能是某个回文子串在前后添加字符，然后再翻转得到。 翻转说明这个回文子串必须全部在回文中心的一边，不妨设它在 $s_u$ 的前面一半。 如果这个回文子串不是 $u$ 的前缀，那么在上面的一条转移会被统计到，所以只需考虑 $s_u$ 的回文前缀即可。 设 $u$ 的长度不超过 $\frac{|s_u|}{2}$ 的最长回文前缀所在的点是 $h_u$。

引理 3：这里如果一个回文前缀不是 $s_u$ 的长度不超过 $\frac{s_u}{2}$ 的最长回文前缀 $s_{h_u}$，那么无需从它转移。

证明：其他长度不超过 $\frac{|s_u|}{2}$ 的回文前缀 $X$ 都是 $s_{h_u}$ 的前缀，$X$ 在后面添加字符得到 $s_u$ 的一半然后翻转得到 $s_u$。那么添加字符到 $h_u$ 时，由引理 1，我们没有通过翻转得到 $s_{h_u}$，此时肯定不优，不如通过 $s_{h_u}$ 转移。 那么有转移 $dp_u \overset{\min}{\longleftarrow} dp_{h_u}+\left(\frac{|s_u|}{2}-|s_{h_u}|\right)+1$。

$dp$ 的初始值：长度为 $2$ 的位置 $dp$ 值为 $2$，偶根 $dp$ 值为 $0$，其他设为极大值。

最后，需要计算 $h$。如果一个串 $s_u$ 通过在后面添加字符得到 $s_v$（即 $u$ 是 $v$ 在 PAM 的 fail 树上的祖先），那么 $s_u$ 的回文前缀也是 $s_v$ 的回文前缀。又 $|s_u|<|s_v|$，那么有 $s_{h_u}$ 是 $s_{h_v}$ 的一个前缀。所以 $h_u$ 在回文自动机上的深度关于 $u$ 的深度有单调性。那么设 $u$ 在 trie 树上的父亲为 $f$、$f$ 到 $u$ 经过字符边 $c$，我们先设 $w=h_f$，不断跳 $fail_w$ 直到 $len_w+2 \le len_u$、$w$ 有 $c$ 儿子且 $s_u$ 最后放得下 $cs_wc$（也就是此时的 $s_w$ 前一个字符是 $c$）或者到了奇根，然后令 $h_u$ 为 $w$ 的 $c$ 儿子即可。

总时间复杂度为 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int trans(char c)
{
	static const string charset="ATCG";
	for(int i=0;i<=3;i++)
	{
		if(charset[i]==c)
			return i;
	}
	return -1;
}
struct PalimdromeAutomaton
{
	struct Node
	{
		int ch[4];
		int len;
		int fth;
		int fil,hlf;
	};
	string s;
	vector<Node> t;
	int lst;
	int newNode()
	{
		t.push_back((Node){{0},0,0,0,0});
		return t.size()-1;
	}
	PalimdromeAutomaton()
	{
		s="";
		t.clear();
		newNode();
		newNode(),newNode();
		t[1].fil=2,t[2].fil=1;
		t[1].len=-1,t[2].len=0;
		t[1].hlf=1,t[2].hlf=2;
		lst=2;
	}
	int findFail(int u,int pos,char c)
	{
		while(u!=1&&s[pos-t[u].len-1]!=c)
			u=t[u].fil;
		return u;
	}
	void insert(char c)
	{
		int x=trans(c);
		s+=c;
		int f=findFail(lst,s.size()-1,c);
		if(!t[f].ch[x])
		{
			int u=newNode();
			t[u].len=t[f].len+2;
			int tmp=findFail(t[f].fil,s.size()-1,c);
			t[u].fil=(t[tmp].ch[x]?t[tmp].ch[x]:2);
			if(t[u].len<=1)
				t[u].hlf=2;
			else
			{
				int v=t[f].hlf;
				while(v!=1&&(t[v].len+2>t[u].len/2||!t[v].ch[x]||s[s.size()-t[v].len-2]!=c))
					v=t[v].fil;
				t[u].hlf=t[v].ch[x];
			}
			t[f].ch[x]=u;
			t[u].fth=f;
		}
		lst=t[f].ch[x];
	}
};
PalimdromeAutomaton pam;
int dp[110000];
void calcDP()
{
	memset(dp,127,sizeof(dp));
	dp[2]=0;
	for(int i=0;i<=3;i++)
	{
		dp[pam.t[2].ch[i]]=2;
	}
	for(int i=1;i<pam.t.size();i++)
	{
		if(pam.t[i].len%2==1||pam.t[i].len<=2)
			continue;
		if(pam.t[pam.t[i].fth].len%2==0)
			dp[i]=min(dp[i],dp[pam.t[i].fth]+1);
		if(pam.t[pam.t[i].hlf].len%2==0)
			dp[i]=min(dp[i],dp[pam.t[i].hlf]+pam.t[i].len/2-pam.t[pam.t[i].hlf].len+1);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		string s;
		cin>>s;
		pam=PalimdromeAutomaton();
		for(int i=0;i<s.size();i++)
		{
			pam.insert(s[i]);
		}
		calcDP();
		int ans=1e9;
		for(int i=1;i<pam.t.size();i++)
		{
			if(pam.t[i].len%2==0)
			{
				ans=min(ans,(int)(s.size()-pam.t[i].len+dp[i]));
			}
		}
		cout<<ans<<'\n';
	}
}