差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:王智彪:回文自动机 [2021/07/31 00:30]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:回文自动机 [2021/08/01 22:28] (当前版本)
王智彪
@@ 行 98: / 行 98: @@
 我们还有 $t$ 是回文串 $s$ 的 $border(|s|≤2|t|)$ ， $s$ 是回文串当且仅当 $t$ 是回文串。如果 $s$ 是回文串，显然根据上面的定理， $t$ 是回文串，如果 $t$ 是回文串，画了一下挺抽象的当然也是显然的。
+还有 $t$ 是回文串 $s$ 的 $border$ ，则 $|s|-|t|$ 是 $s$ 的周期， $|s|-|t|$ 为 $s$ 的最小周期，当且仅当 $t$ 是 $s$ 的最长回文真后缀。
+还有 $x$ 是一个回文串， $y$ 是 $x$ 的最长回文真后缀， $z$ 是 $y$ 的最长回文真后缀。令 $u,v$ 分别为满足 $x=uy,y=vz$ 的字符串，则有：
+$1.|u|≥|v|$ 。
+证明： $|u|=|x|-|y|$ ，是 $x$ 的最小周期，同样也是 $y$ 的周期，又因为 $v$ 是 $y$ 的最小周期，所以 $|u|≥|v|$ 。
+$2.$ 如果 $|u|＞|v|$ ， $|u|＞|z|$ 。
+$3.$ 如果 $|u|=|v|$ ， $u=v$ 。
+.[[https://www.luogu.com.cn/problem/P4555]]
+==== 题意 ====
+给定一个字符串 $S$ ，求最长双回文子串 $T$ ，双回文串即可以拆成两个非空的回文串。
+==== 题解 ====
+显然 $T$ 拆成两个小回文串，是有分割点的，我们枚举分割点，然后相当于求一个在这个位置截止的最长回文串和这个位置开始的最长回文串，其实我们可以倒着求一下，所以只求这个位置结束的最长回文串就可以了。如果只求一边比如 $aaaaa$ ，它不会存第二个位置之后的最长回文串，也就是只求一边是算不全的，还是得算两边的。
+<hidden 代码>
+<code cpp>
+#include <bits/stdc++.h>
+using namespace std;
+const int maxn=100100;
+struct PAM {
+	char s[maxn];
+	int len[maxn],n,num[maxn],fail[maxn],last,cur,pos,trie[maxn][26],tot,m[maxn];
+	void init() {
+		memset(s,0,sizeof(s));
+		memset(len,0,sizeof(len));
+		memset(num,0,sizeof(num));
+		memset(fail,0,sizeof(fail));
+		memset(trie,0,sizeof(trie));
+		memset(m,0,sizeof(m));
+		n=0;last=0;cur=0;pos=0;tot=1;
+		fail[0]=1;len[1]=-1;
+	}
+	int getfail(int x,int i) {
+		while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
+		return x;
+	}
+	void solve() {
+		for(int i=0; i<=n-1; i++) {
+			pos=getfail(cur,i);
+			if(!trie[pos][s[i]-'a']) {
+				fail[++tot]=trie[getfail(fail[pos],i)][s[i]-'a'];
+				trie[pos][s[i]-'a']=tot;
+				len[tot]=len[pos]+2;
+				num[tot]=num[fail[tot]]+1;
+			}
+			cur=trie[pos][s[i]-'a'];
+			m[i]=len[cur];
+		}
+	}
+} p,q;
+int main() {
+	p.init();q.init();
+	scanf("%s",p.s);
+	p.n=strlen(p.s);
+	q.n=p.n;
+	for(int i=0;i<p.n;i++){
+		q.s[i]=p.s[p.n-1-i];
+	}
+	p.solve();
+	q.solve();
+	int ans=0;
+	for(int i=0;i<p.n-1;i++){
+		if(p.m[i]+q.m[p.n-2-i]>ans){
+			ans=p.m[i]+q.m[p.n-2-i];
+		}
+	}
+	printf("%d",ans);
+	return 0;
+}
+</code>
+</hidden>
+.[[https://www.luogu.com.cn/problem/P4287]]
+==== 题意 ====
+给一个字符串 $S$ ，让求一个双倍回文串，这里的双倍回文串要求必须是 $RR^{T}RR^{T}$ 形式的。
+==== 题解 ====
+我们发现这样的子串长度一定是 $4$ 的倍数，并且不超过自己一半长度的最长的失配串的长度一定正好是一半。于是我们重新搞一个 $f$ 数组，记录不超过自己一半长度的最长失配串，如果在找 $fail$ 的时候，发现不到一半，直接赋值成 $fail$ 指针就好了，不然我们需要走 $fail$ 指针，直到长度不到一半为止。
+<hidden 题解>
+<code cpp>
+void solve() {
+		for(int i=0; i<=n-1; i++) {
+			pos=getfail(cur,i);
+			if(!trie[pos][s[i]-'a']) {
+				fail[++tot]=trie[getfail(fail[pos],i)][s[i]-'a'];
+				trie[pos][s[i]-'a']=tot;
+				len[tot]=len[pos]+2;
+				num[tot]=num[fail[tot]]+1;
+				if(len[fail[tot]]<=len[tot]>>1) f[tot]=fail[tot];
+				else{
+					int poss=f[pos];//仿照上面的
+					while(len[poss]+2>len[tot]/2||s[i]!=s[i-len[poss]-1]) poss=fail[poss];//仿照上面的函数len[poss]是没加上两边的串所以再加上两边的大于一半就得跑fail指针
+					f[tot]=trie[poss][s[i]-'a'];//仿照上面的
+				}
+			}
+			cur=trie[pos][s[i]-'a'];
+		}
+	}
+int main() {
+	p.init();
+	int nn;
+	scanf("%d",&nn);
+	scanf("%s",p.s);
+	p.n=strlen(p.s);
+	p.solve();
+	for(int i=2;i<=p.tot;i++){
+		if(p.len[i]%4==0&&p.len[p.f[i]]==p.len[i]>>1){//长度正好是一半
+			p.Ans=max(p.Ans,p.len[i]);
+		}
+	}
+	printf("%d\n",p.Ans);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具