CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:字符串_3 [2020/08/30 21:51]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:字符串_3 [2020/09/02 10:52] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
 ====== 字符串 3 ======
-===== 后缀数组 =====
+===== 后缀数组(SA) =====
 ==== 算法简介 ====
@@ 行 33: / 行 33: @@
 根据该结论建立 $\text{ST}$ 表即可 $O(1)$ 求解每个后缀 $\text{LCP}$ 的询问。
-接下来考虑任意两个子串 $S_1=S[a,b],S_2=S[c,d]$ 的大小。
+考虑如何比较任意两个子串 $S_1=S[a,b],S_2=S[c,d]$ 的大小。
 若 $\text{LCP}(S[a,n],S[b,n])\ge \min(S_1,S_2)$，显然只需要比较 $|S_1|,|S_2|$；否则比较 $rk_a,rk_c$ 即可。
+下面给出后缀数组模板。
 <code cpp>
 namespace SA{
-	int sa[MAXN],rk[MAXN],height[MAXN],x[MAXN],y[MAXN],c[MAXN];
+	int sa[MAXN],rk[MAXN],height[MAXN],X[MAXN],Y[MAXN],c[MAXN];
-	void get_sa(char *s,int n,int m){//s下标从1开始
+	int d[MAXN][MAXM],lg2[MAXN];
+	void get_sa(char *s,int n,int m){//s下标从1开始
+		int *x=X,*y=Y;
 		_rep(i,0,m)c[i]=0;
 		_rep(i,1,n)c[x[i]=s[i]]++;
@@ 行 67: / 行 71: @@
 			height[rk[i]]=k;
 		}
+	}
+	void build_st(int n){
+		lg2[1]=0;
+		_rep(i,2,n)
+		lg2[i]=lg2[i>>1]+1;
+		_rep(i,1,n)
+		d[i][0]=height[i];
+		for(int j=1;(1<<j)<=n;j++){
+			_rep(i,1,n+1-(1<<j))
+			d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
+		}
+	}
+	int lcp(int a,int b){//a!=b
+		int lef=rk[a],rig=rk[b];
+		if(lef>rig)swap(lef,rig);lef++;
+		int len=rig-lef+1;
+		return min(d[lef][lg2[len]],d[rig-(1<<lg2[len])+1][lg2[len]]);
 	}
 }
@@ 行 347: / 行 368: @@
 给定一个字符串 $S$ 和序列 $v$，字符串对 $(S[a,b],S[c,d])$ 的权值为 $v_av_b$。
-对 $0\le i\lt n$，询问满足 $\text{LCP}(S[a,b],S[c,d])\ge i$ 的所有字符串对的个数和最大权值。
+对 $0\le i\lt n$，询问满足 $S[a,a+i-1]=S[b,b+i-1]$ 的所有字符串对的个数和最大权值。
 == 题解 ==
-将 $\text{height}_i$ 视为连接 $sa_i$ 和 $sa_{i-1}$ 的一条边。
+枚举子串的右端点，设 $\text{LCP}(S[sa_a,n],S[sa_b,n])=k$，显然 $S[sa_a,sa_b+i-1]=S[sa_b,sa_b+i-1](1\le i\le k)$ 均成立。
+不妨只考虑字符串 $S[sa_a,sa_a+k-1]=S[sa_b,sa_b+k-1]$ 对 $i=k$ 的答案的贡献，最后求后缀和以及后缀最大值即可。
+将 $\text{height}_i$ 视为连接 $sa_i$ 和 $sa_{i-1}$ 的一条边，将边按 $\text{height}$ 值从大到小排序。
+然后依次向图中加入每条边，于是每条新加入的边一定是最短边，决定了两个连通块间的字符串对的 $\text{LCP}$。
+于是并查集维护点集大小，点集中的 $v$ 的最大值和最小值(因为可能出现负数乘以负数的情况) 即可。
+时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5;
+namespace SA{
+	int sa[MAXN],rk[MAXN],height[MAXN],x[MAXN],y[MAXN],c[MAXN];
+	void get_sa(char *s,int n,int m){
+		_rep(i,0,m)c[i]=0;
+		_rep(i,1,n)c[x[i]=s[i]]++;
+		_rep(i,1,m)c[i]+=c[i-1];
+		for(int i=n;i;i--)sa[c[x[i]]--]=i;
+		for(int k=1;k<n;k<<=1){
+			int pos=0;
+			_rep(i,n-k+1,n)y[++pos]=i;
+			_rep(i,1,n)if(sa[i]>k)y[++pos]=sa[i]-k;
+			_rep(i,0,m)c[i]=0;
+			_rep(i,1,n)c[x[i]]++;
+			_rep(i,1,m)c[i]+=c[i-1];
+			for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
+			swap(x,y);
+			pos=0,y[n+1]=0;
+			_rep(i,1,n)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?pos:++pos;
+			if(pos==n)break;
+			m=pos;
+		}
+		_rep(i,1,n)rk[sa[i]]=i;
+	}
+	void get_height(char *s,int n){
+		for(int i=1,k=0;i<=n;i++){
+			if(k)k--;
+			while(s[i+k]==s[sa[rk[i]-1]+k])k++;
+			height[rk[i]]=k;
+		}
+	}
+}
+char buf[MAXN];
+int p[MAXN],sz[MAXN],maxv[MAXN],minv[MAXN];
+LL ans1[MAXN],ans2[MAXN];
+pair<int,int> edge[MAXN];
+int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);}
+bool cmp(const pair<int,int> &a,const pair<int,int> &b){
+	return a.first>b.first;
+}
+int main()
+{
+	int n=read_int();
+	scanf("%s",buf+1);
+	SA::get_sa(buf,n,'z');
+	SA::get_height(buf,n);
+	_rep(i,1,n){
+		maxv[i]=minv[i]=read_int();
+		p[i]=i,sz[i]=1;
+	}
+	_for(i,0,n)ans2[i]=-1e18;
+	_for(i,1,n)edge[i]=make_pair(SA::height[i+1],i+1);
+	sort(edge+1,edge+n,cmp);
+	_for(i,1,n){
+		int u=SA::sa[edge[i].second],v=SA::sa[edge[i].second-1],k=edge[i].first;
+		int x=Find(u),y=Find(v);
+		ans1[k]+=1LL*sz[x]*sz[y];
+		ans2[k]=max(ans2[k],max(1LL*maxv[x]*maxv[y],1LL*minv[x]*minv[y]));
+		p[x]=y;
+		sz[y]+=sz[x];
+		maxv[y]=max(maxv[y],maxv[x]);
+		minv[y]=min(minv[y],minv[x]);
+	}
+	for(int i=n-1;i;i--){
+		ans1[i-1]+=ans1[i];
+		ans2[i-1]=max(ans2[i-1],ans2[i]);
+	}
+	_for(i,0,n){
+		space(ans1[i]);
+		enter(ans1[i]?ans2[i]:0);
+	}
+	return 0;
+}
+</code>
+</hidden>
+=== 例题六 ===
+[[https://www.luogu.com.cn/problem/P3763|洛谷p3763]]
+== 题意 ==
+给定一个文本串 $S_0$ 和模式串 $S$，问 $S_0$ 中 $S$ 的近似匹配次数。
+定义 $S_0[i,i+n-1]$ 与 $S[1,n]$ 近似匹配当且仅当 $S_0[i,i+n-1]$ 与 $S[1,n]$ 至多有 $3$ 个不同的字符。
+== 题解 ==
+由于匹配最多只允许 $3$ 个字符不同，考虑暴力枚举 $S_0$ 右端点，然后尝试匹配。
+将串拼接为 $S_0+\text{#}+S$ 即可 $O(1)$ 完成相应 $\text{LCP}$ 查询，然后每次跳 $\text{LCP}$ 的长度继续匹配即可。
+时间复杂度 $O(n\log n)$，主要在于后缀数组和 $\text{ST}$ 表建立，常数较大。
+ps.这题也有 $\text{FFT}$ 的解法，有兴趣的可以查看这篇[[https://www.luogu.com.cn/blog/My-luoguBuoke-HZR/solution-p3763#|题解]]。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,MAXM=20;
+namespace SA{
+	int sa[MAXN],rk[MAXN],height[MAXN],x[MAXN],y[MAXN],c[MAXN];
+	int d[MAXN][MAXM],lg2[MAXN];
+	void get_sa(char *s,int n,int m){
+		_rep(i,0,m)c[i]=0;
+		_rep(i,1,n)c[x[i]=s[i]]++;
+		_rep(i,1,m)c[i]+=c[i-1];
+		for(int i=n;i;i--)sa[c[x[i]]--]=i;
+		for(int k=1;k<n;k<<=1){
+			int pos=0;
+			_rep(i,n-k+1,n)y[++pos]=i;
+			_rep(i,1,n)if(sa[i]>k)y[++pos]=sa[i]-k;
+			_rep(i,0,m)c[i]=0;
+			_rep(i,1,n)c[x[i]]++;
+			_rep(i,1,m)c[i]+=c[i-1];
+			for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
+			swap(x,y);
+			pos=0,y[n+1]=0;
+			_rep(i,1,n)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?pos:++pos;
+			if(pos==n)break;
+			m=pos;
+		}
+		_rep(i,1,n)rk[sa[i]]=i;
+	}
+	void get_height(char *s,int n){
+		for(int i=1,k=0;i<=n;i++){
+			if(k)k--;
+			while(s[i+k]==s[sa[rk[i]-1]+k])k++;
+			height[rk[i]]=k;
+		}
+	}
+	void build_st(int n){
+		lg2[1]=0;
+		_rep(i,2,n)
+		lg2[i]=lg2[i>>1]+1;
+		_rep(i,1,n)
+		d[i][0]=height[i];
+		for(int j=1;(1<<j)<=n;j++){
+			_rep(i,1,n+1-(1<<j))
+			d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
+		}
+	}
+	int lcp(int a,int b){
+		int lef=rk[a],rig=rk[b];
+		if(lef>rig)swap(lef,rig);lef++;
+		int len=rig-lef+1;
+		return min(d[lef][lg2[len]],d[rig-(1<<lg2[len])+1][lg2[len]]);
+	}
+}
+char buf[MAXN];
+int main()
+{
+	int T=read_int();
+	while(T--){
+		scanf("%s",buf+1);
+		int len1=strlen(buf+1);
+		buf[len1+1]='#';
+		scanf("%s",buf+len1+2);
+		int n=strlen(buf+1),len2=n-len1-1;
+		SA::get_sa(buf,n,'z');
+		SA::get_height(buf,n);
+		SA::build_st(n);
+		int ans=0;
+		_rep(i,1,len1-len2+1){
+			int pos=1,cnt=0;
+			while(cnt<=3){
+				pos+=SA::lcp(i+pos-1,len1+1+pos);
+				if(pos>len2)break;
+				pos++;cnt++;
+			}
+			if(cnt<=3)
+			ans++;
+		}
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
+=== 例题七 ===
+[[https://www.luogu.com.cn/problem/P4248|洛谷p4248]]
+== 题意 ==
+给定字符串 $S$，设 $T_i=S[i,n]$，求
+$$\sum_{1\le i\lt j\le n}|T_i|+|T_j|+2\times \text{LCP}(T_i,T_j)$$
+== 题解 ==
+$$\sum_{1\le i\lt j\le n}|T_i|+|T_j|-2\times \text{LCP}(T_i,T_j)=(n-1)\sum_{i=1}^n|T_i|-2\times \sum_{1\le i\lt j\le n}\text{LCP}(T_i,T_j)=\frac {(n-1)n(n+1)}2-2\times \sum_{1\le i\lt j\le n}\text{LCP}(T_i,T_j)$$
+发现只要维护后面部分即可。
+考虑单调栈维护，设 $\text{dp}_i=\sum_{1\le j\lt i}\text{LCP}(T_i,T_j)$，用单调栈维护 $height_i$ 数组。
+于是对所有 $i$，可以均摊 $O(1)$ 得到最大的 $j\lt i$ 满足 $\text{hieght}_j\le \text{height}_i$。
+根据 $\text{height}$ 性质，发现 $j\lt k\le i$ 时 $\text{LCP}(T_k,T_i)=\text{height}_i$，而 $k\le j$ 时 $\text{LCP}(T_k,T_i)=\text{LCP}(T_k,T_j)$。
+于是 $\text{dp}_i=\sum_{1\le j\lt i}\text{LCP}(T_i,T_j)=\text{dp}_j+(i-j)\text{height}_i$。
+另外该题也可以用笛卡尔树或并查集等维护。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5,MAXM=20;
+namespace SA{
+	int sa[MAXN],rk[MAXN],height[MAXN],x[MAXN],y[MAXN],c[MAXN];
+	void get_sa(char *s,int n,int m){
+		_rep(i,0,m)c[i]=0;
+		_rep(i,1,n)c[x[i]=s[i]]++;
+		_rep(i,1,m)c[i]+=c[i-1];
+		for(int i=n;i;i--)sa[c[x[i]]--]=i;
+		for(int k=1;k<n;k<<=1){
+			int pos=0;
+			_rep(i,n-k+1,n)y[++pos]=i;
+			_rep(i,1,n)if(sa[i]>k)y[++pos]=sa[i]-k;
+			_rep(i,0,m)c[i]=0;
+			_rep(i,1,n)c[x[i]]++;
+			_rep(i,1,m)c[i]+=c[i-1];
+			for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
+			swap(x,y);
+			pos=0,y[n+1]=0;
+			_rep(i,1,n)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?pos:++pos;
+			if(pos==n)break;
+			m=pos;
+		}
+		_rep(i,1,n)rk[sa[i]]=i;
+	}
+	void get_height(char *s,int n){
+		for(int i=1,k=0;i<=n;i++){
+			if(k)k--;
+			while(s[i+k]==s[sa[rk[i]-1]+k])k++;
+			height[rk[i]]=k;
+		}
+	}
+}
+char buf[MAXN];
+pair<int,int> Stack[MAXN];
+LL dp[MAXN];
+int main()
+{
+	scanf("%s",buf+1);
+	int n=strlen(buf+1);
+	SA::get_sa(buf,n,'z');
+	SA::get_height(buf,n);
+	LL ans=1LL*(n-1)*n*(n+1)/2;
+	int top=0;
+	Stack[0]=make_pair(0,0);
+	_rep(i,1,n){
+		while(top&&Stack[top].second>SA::height[i])top--;
+		dp[i]=dp[Stack[top].first]+1LL*(i-Stack[top].first)*SA::height[i],ans-=dp[i]*2;
+		Stack[++top]=make_pair(i,SA::height[i]);
+	}
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具