差别

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

--- 2020-2021:teams:legal_string:jxm2001:字符串_1 [2020/08/26 20:10]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:字符串_1 [2020/08/27 11:38] (当前版本)
jxm2001
@@ 行 21: / 行 21: @@
 如果 $s_{i+1}\neq s_{f(i)+1}$，则只能考虑第二长的真前后缀，暂时记为 $j$。
-于是有 $s[1,j]=s[i-j+1,i]=s[f(i)-j+1,f(i)]$，发现 $j$ 是 $s[1,f(i)]$ 的真前后缀，于是有 $j=f(f(i))$。
+根据已知，有 $s[1,j]=s[i-j+1,i]=s[f(i)-j+1,f(i)]$。
+发现 $j$ 是 $s[1,f(i)]$ 的真前后缀，于是有 $j=f(f(i))$。
 不停尝试，直到 $j=0$ 即没有满足条件真前后缀，可以停止尝试。
@@ 行 209: / 行 211: @@
 同时对所有满足条件的 $j$，不难发现有 $t[1,m]$ 的长度为 $j$ 的前后缀相同。
-由于无法判断 $j$ 是否满足上述条件，于是暴力跳 $t$ 的 $f$ 函数枚举每个 $j$ 即可。
+由于无法判断 $j$ 是否满足上述条件，于是暴力跳 $t$ 的 $f$ 函数枚举每个 $j$ 即可。总时间复杂度 $O(nm)$。
-总时间复杂度 $O(nm)$。
 <hidden 查看代码>
@@ 行 249: / 行 249: @@
 	}
 	enter(dp1[n]);
+	return 0;
+}
+</code>
+</hidden>
+===== Z 函数 =====
+==== 算法简介 ====
+给定两个字符串 $S_1,S_2$，查询 $S_1,S_2$ 与 $S_2$ 每个后缀的 $\text{LCP}$。时间复杂度 $O(|S_1|+|S_2|)$。
+==== 算法实现 ====
+设 $z(i)$ 表示 $S[1,|S|],S[i,|S|]$ 的 $\text{LCA}$ 长度，先考虑求模式串 $S_2$ 的 $z$ 函数。
+假设 $i\lt l$ 的 $z(i)$ 已知，考虑求 $z(l)$。直接暴力拓展 $[l,r]$，直到取到 $s_r=s_{r-l+1}$ 的最大值，易知此时 $z(l)=r-l+1$。
+接下来考虑区间 $i\in [l+1,r]$，首先由于 $s_{r+1}\neq s_{r-l+2}$，于是 $z(i)\le r-i+1$。
+同时由于 $s[l,r]$ 与 $s[1,r-l+1]$ 完全相同，于是若 $z(i-l+1)\le r-i+1$，显然有 $z(i)=z(i-l+1)$，否则有 $z(i)=r-i+1$。
+于是可以在 $O(r-l)$ 时间求出 $r-l+1$ 个 $z$ 函数的值，于是求 $z$ 函数的时间复杂度为 $O(|S_2|)$。
+接下来考虑求 $S_1$ 与 $S_2$ 每个后缀的 $\text{LCP}$，同样可以按上述方法求取，时间复杂度 $O(|S_1|)$。于是总时间复杂度 $O(|S_1|+|S_2|)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e7+5;
+namespace KMP{
+	int z[MAXN],p[MAXN];
+	void cmp(char *s1,int n,char *s2,int m){//s下标从1开始
+		z[1]=m;
+		_rep(i,2,m)z[i]=0;
+		for(int i=2,l=0,r=0;i<=m;i++){
+			if(i<=r)z[i]=min(z[i-l+1],r-i+1);
+			while(i+z[i]<=m&&s2[z[i]+1]==s2[i+z[i]])z[i]++;
+			if(i+z[i]-1>r)l=i,r=i+z[i]-1;
+		}
+		_rep(i,1,n)p[i]=0;
+		for(int i=1,l=0,r=0;i<=n;i++){
+			if(i<=r)p[i]=min(z[i-l+1],r-i+1);
+			while(i+p[i]<=n&&s2[p[i]+1]==s1[i+p[i]])p[i]++;
+			if(i+p[i]-1>r)l=i,r=i+p[i]-1;
+		}
+	}
+}
+char a[MAXN],b[MAXN];
+int main()
+{
+	gets(a+1);gets(b+1);
+	int n=strlen(a+1),m=strlen(b+1);
+	KMP::cmp(a,n,b,m);
+	LL ans1=0,ans2=0;
+	_rep(i,1,m)
+	ans1^=1LL*i*(KMP::z[i]+1);
+	_rep(i,1,n)
+	ans2^=1LL*i*(KMP::p[i]+1);
+	enter(ans1);enter(ans2);
+	return 0;
+}
+</code>
+</hidden>
+==== 算法练习 ====
+=== 习题一 ===
+[[https://www.luogu.com.cn/problem/CF126B|CF126B]]
+== 题意 ==
+给定字符串 $S$，求既是 $S$ 的前缀又是 $S$ 的后缀同时又在 $S$ 中间出现过的最长子串。
+== 题解 1 ==
+考虑求出每个位置的 $z$ 函数，然后找到与前缀相同的在中间出现过的最长字串，有 $\text{pre}=\max_{1\lt i \lt n}(\min(z(i),n-i))$。
+接下来从大到小枚举每个与前缀相同的后缀，判定条件为 $i+z(i)-1=n$。如果该后缀长度小于 $\text{pre}$，则得到答案。时间复杂度 $O(|S|)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e6+5;
+namespace KMP{
+	int z[MAXN];
+	void get_z(char *s,int n){
+		z[1]=n;
+		_rep(i,2,n)z[i]=0;
+		for(int i=2,l=0,r=0;i<=n;i++){
+			if(i<=r)z[i]=min(z[i-l+1],r-i+1);
+			while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]])z[i]++;
+			if(i+z[i]-1>r)l=i,r=i+z[i]-1;
+		}
+	}
+}
+char s[MAXN];
+int main()
+{
+	gets(s+1);
+	int n=strlen(s+1);
+	KMP::get_z(s,n);
+	int pre=0,ans=0;
+	_for(i,2,n)pre=max(pre,min(KMP::z[i],n-i));
+	_rep(i,2,n)if(i+KMP::z[i]-1==n&&KMP::z[i]<=pre){
+		ans=KMP::z[i];
+		break;
+	}
+	if(!ans)puts("Just a legend");
+	else
+	_rep(i,1,ans)putchar(s[i]);
+	return 0;
+}
+</code>
+</hidden>
+== 题解 2 ==
+考虑求出每个位置的 $f$ 函数，同样找到与前缀相同的在中间出现过的最长字串，有 $\text{pre}=\max_{1\lt i \lt n}f(i)$。
+接下来从大到小枚举每个与前缀相同的后缀，初始为 $f(n)$，然后不断迭代 $f$ 即可。如果该后缀长度小于 $\text{pre}$，则得到答案。时间复杂度 $O(|S|)$。
+=== 习题二 ===
+[[https://www.luogu.com.cn/problem/CF432D|CF432D]]
+== 题意 ==
+给你一个长度为 $n$ 的字符串。定义“完美子串”既是它的前缀也是它的后缀，求“完美子串”的个数且统计这些子串的在字符串中出现的次数。
+== 题解 1 ==
+考虑求出每个位置的 $z$ 函数，统计每个前缀出现次数。关于 $z$ 函数统计前缀次数，如果 $s[l,r]=s[1,r-l+1]$，显然有 $s[l,r-1]=s[1,r-l]$。
+于是可以直接用桶维护 $z$ 函数，然后求后缀和。
+然后从大到小枚举每个与前缀相同的后缀并记录答案，判定条件为 $i+z(i)-1=n$。时间复杂度 $O(|S|)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+namespace KMP{
+	int z[MAXN];
+	void get_z(char *s,int n){
+		z[1]=n;
+		_rep(i,2,n)z[i]=0;
+		for(int i=2,l=0,r=0;i<=n;i++){
+			if(i<=r)z[i]=min(z[i-l+1],r-i+1);
+			while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]])z[i]++;
+			if(i+z[i]-1>r)l=i,r=i+z[i]-1;
+		}
+	}
+}
+int c[MAXN];
+char s[MAXN];
+int main()
+{
+	gets(s+1);
+	int n=strlen(s+1);
+	KMP::get_z(s,n);
+	stack<int> s;
+	_rep(i,1,n){
+		if(i+KMP::z[i]-1==n)
+		s.push(KMP::z[i]);
+		c[KMP::z[i]]++;
+	}
+	for(int i=n;i;i--)c[i-1]+=c[i];
+	enter(s.size());
+	while(!s.empty()){
+		printf("%d %d\n",s.top(),c[s.top()]);
+		s.pop();
+	}
+	return 0;
+}
+</code>
+</hidden>
+== 题解 2 ==
+考虑求出每个位置的 $f$ 函数，统计每个前缀出现次数。
+然后从大到小枚举每个与前缀相同的后缀并记录答案，初始为 $n$，然后不断迭代 $f$ 即可。时间复杂度 $O(|S|)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+namespace KMP{
+	int f[MAXN];
+	void get_f(char *s,int n){
+		int pos=0;
+		f[1]=0;
+		_rep(i,2,n){
+			while(pos&&s[i]!=s[pos+1])pos=f[pos];
+			if(s[i]==s[pos+1])pos++;
+			f[i]=pos;
+		}
+	}
+}
+char s[MAXN];
+int c[MAXN];
+int main()
+{
+	gets(s+1);
+	int n=strlen(s+1);
+	KMP::get_f(s,n);
+	_rep(i,1,n)c[KMP::f[i]]++;
+	stack<pair<int,int> >pt;
+	for(int i=n;i;i--)c[KMP::f[i]]+=c[i];
+	for(int i=n;i;i=KMP::f[i])
+	pt.push(make_pair(i,c[i]+1));
+	enter(pt.size());
+	while(!pt.empty()){
+		printf("%d %d\n",pt.top().first,pt.top().second);
+		pt.pop();
+	}
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具