差别

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

--- 2020-2021:teams:legal_string:jxm2001:字符串_4 [2020/09/02 10:16]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:字符串_4 [2020/09/04 11:28] (当前版本)
jxm2001
@@ 行 5: / 行 5: @@
 ==== 简介 ====
-一种用于解决各种字符串问题的数据结构，时间复杂度 $O(n)$，空间复杂度 $O(\sum n)$。
+一种用于解决各种字符串问题的数据结构，时间复杂度 $O(n)$。
 ==== 性质 ====
@@ 行 77: / 行 77: @@
 === 习题一 ===
-[[https://www.luogu.com.cn/problem/P3804|p3804]]
+[[https://www.luogu.com.cn/problem/P3804|洛谷p3804]]
-== 题意 ==
+**题意**
-给定字符串 $S$，求 $S$ 中出现字数不为 $1$ 的子串乘以子串长度的最大值。
+给定字符串 $S$，求 $S$ 中出现次数不为 $1$ 的子串乘以子串长度的最大值。
-== 题解 1 ==
+**SAM 题解**
 根据 $\text{SAM}$ 的性质四，不难得到过程，时间复杂度 $O(n)$。
@@ 行 146: / 行 146: @@
 </hidden>
-== 题解 2 ==
+**SA 题解**
 考虑 $\text{SA}$ 维护得到 $\text{height}$ 数组，从大到小添加 $\text{height}$ 数组代表的连边同时并查集维护集合大小即可，时间复杂度 $O(n\log n)$。
@@ 行 152: / 行 152: @@
 === 习题二 ===
-[[https://www.luogu.com.cn/problem/P4070|p4070]]
+[[https://www.luogu.com.cn/problem/P4070|洛谷p4070]]
-== 题意 ==
+**题意**
 给定一个空串 $S$，每次向 $S$ 末尾添加一个字符串，求每次操作后 $S$ 中本质不同的子串个数。
-== 题解 1 ==
+**SAM 题解**
-根据 $\text{SAM}$ 的性质三，不难得到过程，但注意需要 $\text{map}$ 存图，时间复杂度 $O(n\log n)$。
+根据 $\text{SAM}$ 的性质三，不难得到过程，但注意需要字符集较大时需要 $\text{map}$ 存图，时间复杂度 $O(n\log n)$。
 <hidden 查看代码>
@@ 行 200: / 行 200: @@
 		enter(ans);
 	}
+	return 0;
+}
+</code>
+</hidden>
+**SA 题解**
+如果向后加入字符将影响所所有后缀以及对应的 $\text{height}$ 数组。于是考虑将字符串翻转，本质不同的串个数并不会改变。
+但是向后加入字符操作转化为向前加入字符操作，而向前加入新字符操作只是增加一个后缀，并不会影响之前的 $\text{height}$ 数组。
+于是可以利用平衡树和 $\text{ST}$ 表， $O(\log n)$ 时间复杂度计算每次新加入字符产生的本质不同的字符串个数。总时间复杂 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+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(int *s,int n,int m){
+		int *x=X,*y=Y;
+		_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(int *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 lef,int rig){
+		int len=rig-(++lef)+1;
+		return min(d[lef][lg2[len]],d[rig-(1<<lg2[len])+1][lg2[len]]);
+	}
+}
+int buf[MAXN],a[MAXN];
+set<int> s;
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n)buf[i]=a[i]=read_int();
+	reverse(buf+1,buf+n+1);
+	sort(a+1,a+n+1);
+	int m=unique(a+1,a+n+1)-a;
+	_rep(i,1,n)buf[i]=lower_bound(a+1,a+m,buf[i])-a;
+	SA::get_sa(buf,n,m);
+	SA::get_height(buf,n);
+	SA::build_st(n);
+	LL ans=0;
+	for(int i=n;i;i--){
+		s.insert(SA::rk[i]);
+		set<int>::iterator it=s.find(SA::rk[i]);
+		int lcp=0;
+		if(it!=s.begin()){
+			lcp=max(lcp,SA::lcp(*(--it),SA::rk[i]));
+			it++;
+		}
+		if((++it)!=s.end())
+		lcp=max(lcp,SA::lcp(SA::rk[i],*it));
+		ans+=n+1-i-lcp;
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
+=== 习题三 ===
+[[https://www.luogu.com.cn/problem/SP1811|SP1811]]
+**题意**
+给定两个串，求两个串的最长公共子串($\text{LCS}$)。
+**SAM 题解**
+考虑将一个串压入 $\text{SAM}$，另一个串在 $\text{SAM}$ 上匹配。
+如果存在 $ch[pos][c]$，则直接匹配，且匹配长度 $+1$。否则考虑尽可能地保留后缀，于是不断跳 $\text{parent}$ 树。
+由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于父节点等价类中最长串，于是当前串一定能与父节点最长串匹配。
+于是跳 $\text{parent}$ 树过程中如果遇到 $ch[pos][c]$ 存在的情况，则跳到 $ch[pos][c]$ 结点，匹配长度变为 $len_\text{pos}+1$。
+每次失配向上跳使得匹配长度变短，而匹配长度最多增加 $|T|$ 次，于是失配的均摊复杂度为 $O(1)$。总时间复杂度 $O(n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5;
+struct SAM{
+	int ch[MAXN][26],fa[MAXN],len[MAXN],last,cnt;
+	void extend(int c){
+		int p=last,np=++cnt;
+		last=np,len[np]=len[p]+1;
+		for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
+		if(!p)fa[np]=1;
+		else{
+			int q=ch[p][c];
+			if(len[q]==len[p]+1)fa[np]=q;
+			else{
+				int nq=++cnt;len[nq]=len[p]+1;
+				memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];
+				fa[q]=fa[np]=nq;
+				for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
+			}
+		}
+	}
+	void init(char *s,int n){
+		last=cnt=1;
+		mem(ch[1],0);
+		_for(i,0,n)
+		extend(s[i]-'a');
+	}
+	int lcs(char *s,int n){
+		int pos=1,cur=0,ans=0;
+		_for(i,0,n){
+			int c=s[i]-'a';
+			if(ch[pos][c])cur++,pos=ch[pos][c];
+			else{
+				while(pos&&!ch[pos][c])pos=fa[pos];
+				if(!pos)cur=0,pos=1;
+				else
+				cur=len[pos]+1,pos=ch[pos][c];
+			}
+			ans=max(ans,cur);
+		}
+		return ans;
+	}
+}solver;
+char s[MAXN],t[MAXN];
+int main()
+{
+	scanf("%s%s",s,t);
+	solver.init(s,strlen(s));
+	enter(solver.lcs(t,strlen(t)));
+	return 0;
+}
+</code>
+</hidden>
+**SA 题解**
+将两个串拼接后中间用 $\text{#}$ 字符分隔，然后直接枚举相邻 $sa$ 的 $\text{LCP}$ 即可，注意只有相邻 $sa$ 属于不同串才能产生贡献。
+提前对 $sa$ 进行染色即可，时间复杂度 $O(n\log n)$。
+=== 习题四 ===
+[[https://www.luogu.com.cn/problem/SP1812|SP1812]]
+**题意**
+给定 $n$ 个串，求 $n$ 个串的 $\text{LCS}$。
+**SAM 题解**
+考虑将一个串压入 $\text{SAM}$，其他所有串在 $\text{SAM}$ 上匹配。
+对每个串，记录每个结点匹配的答案，然后每个结点取该结点所有匹配答案的最小值，然后所有结点的最大值即为所求答案。
+注意 $\text{parent}$ 树的子节点可以将答案贡献给父节点，可以每次匹配后根据拓扑序转移答案。时间复杂度 $O(\sum |S|)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5;
+struct SAM{
+	int ch[MAXN][26],fa[MAXN],len[MAXN],last,cnt;
+	int c[MAXN],topu[MAXN],maxv[MAXN],minv[MAXN];
+	void extend(int c){
+		int p=last,np=++cnt;
+		last=np,len[np]=len[p]+1;
+		for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
+		if(!p)fa[np]=1;
+		else{
+			int q=ch[p][c];
+			if(len[q]==len[p]+1)fa[np]=q;
+			else{
+				int nq=++cnt;len[nq]=len[p]+1;
+				memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];
+				fa[q]=fa[np]=nq;
+				for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
+			}
+		}
+	}
+	void init(char *s,int n){
+		last=cnt=1;
+		mem(ch[1],0);
+		_for(i,0,n)
+		extend(s[i]-'a');
+		_rep(i,1,cnt)c[len[i]]++,minv[i]=n;
+		_rep(i,1,cnt)c[i]+=c[i-1];
+		_rep(i,1,cnt)topu[c[len[i]]--]=i;
+	}
+	void lcs(char *s,int n){
+		int pos=1,cur=0,ans=0;
+		_for(i,0,n){
+			int c=s[i]-'a';
+			if(ch[pos][c])cur++,pos=ch[pos][c];
+			else{
+				while(pos&&!ch[pos][c])pos=fa[pos];
+				if(!pos)cur=0,pos=1;
+				else
+				cur=len[pos]+1,pos=ch[pos][c];
+			}
+			maxv[pos]=max(maxv[pos],cur);
+		}
+		for(int i=cnt;i;i--){
+			int u=topu[i];
+			if(maxv[u])maxv[fa[u]]=len[fa[u]];
+			minv[u]=min(minv[u],maxv[u]),maxv[u]=0;
+		}
+	}
+}solver;
+char s[MAXN];
+int main()
+{
+	scanf("%s",s);
+	solver.init(s,strlen(s));
+	while(~scanf("%s",s))
+	solver.lcs(s,strlen(s));
+	int ans=0;
+	_rep(i,1,solver.cnt)
+	ans=max(ans,solver.minv[i]);
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+**SA 题解**
+将 $n$ 个串拼接后中间用 $\text{#}$ 字符分隔，然后对 $sa$ 进行染色，使用滑动窗口维护含有 $n$ 中颜色这个限制。
+用单调队列维护滑动窗口最小值，时间复杂度 $O\left(\sum |S|\log (\sum |S|)\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e6+50;
+namespace SA{
+	int sa[MAXN],rk[MAXN],height[MAXN],X[MAXN],Y[MAXN],c[MAXN];
+	void get_sa(char *s,int n,int m){
+		int *x=X,*y=Y;
+		_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;
+		}
+	}
+}
+int L[12],R[12],vis[12],color[MAXN],cnt,q[MAXN];
+char s[MAXN];
+void add(int c){
+	if(!c)return;
+	vis[c]++;
+	if(vis[c]==1)cnt++;
+}
+void del(int c){
+	if(!c)return;
+	vis[c]--;
+	if(!vis[c])cnt--;
+}
+int main()
+{
+	int n=0,m=0;
+	while(~scanf("%s",s+n+1)){
+		L[++m]=n+1;
+		n+=strlen(s+n+1);
+		R[m]=n;
+		s[++n]='#';
+	}
+	s[n--]='\0';
+	SA::get_sa(s,n,'z');
+	SA::get_height(s,n);
+	_rep(i,1,m)
+	_rep(j,L[i],R[i])
+	color[SA::rk[j]]=i;
+	int ans=0,lef=1,head=0,tail=1;
+	add(color[1]);
+	_rep(i,2,n){
+		while(tail<head&&SA::height[q[head]]>=SA::height[i])head--;
+		q[++head]=i;
+		add(color[i]);
+		if(cnt==m){
+			while(cnt==m)del(color[lef++]);
+			add(color[--lef]);
+		}
+		while(tail<head&&q[tail]<=lef)tail++;//height[lef]是sa[lef-1],sa[lef]之间限制，不需要包含
+		if(cnt==m)ans=max(ans,SA::height[q[tail]]);
+	}
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+=== 习题五 ===
+[[https://www.luogu.com.cn/problem/P3975|洛谷p3975]]
+**题意**
+给定串 $S$，分别求其在不同位置相同子串只算一次和在不同位置相同子串算多次情况下的第 $k$ 小子串。
+**题解**
+先考虑不同位置相同子串算多次情况下的答案，首先易知每个子串出现次数为 $\text{endpos}$ 大小。
+于是可以在 $\text{SAM}$ 上计算出每个结点包含子串数目，然后进行类似名次树的操作，即可得到第 $k$ 小子串。
+对与不同位置相同子串只算一次情况下的答案，将 $\text{endpos}$ 大小强制修改为 $1$ 即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e6+5;
+struct SAM{
+	int ch[MAXN][26],fa[MAXN],len[MAXN],last,cnt;
+	int c[MAXN],topu[MAXN],sz[MAXN];
+	LL sum[MAXN];
+	void extend(int c){
+		int p=last,np=++cnt;
+		last=np,len[np]=len[p]+1,sz[np]=1;
+		for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
+		if(!p)fa[np]=1;
+		else{
+			int q=ch[p][c];
+			if(len[q]==len[p]+1)fa[np]=q;
+			else{
+				int nq=++cnt;len[nq]=len[p]+1;
+				memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];
+				fa[q]=fa[np]=nq;
+				for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
+			}
+		}
+	}
+	void init(char *s,int n){
+		last=cnt=1;
+		mem(ch[1],0);
+		_for(i,0,n)
+		extend(s[i]-'a');
+	}
+	void dfs(int pos,int k){
+		if(k<=sz[pos])return;
+		k-=sz[pos];
+		_for(i,0,26){
+			if(!ch[pos][i])continue;
+			if(sum[ch[pos][i]]<k)k-=sum[ch[pos][i]];
+			else{
+				putchar('a'+i);
+				return dfs(ch[pos][i],k);
+			}
+		}
+	}
+	void query(int opt,int k){
+		_rep(i,1,cnt)c[len[i]]++;
+		_rep(i,1,cnt)c[i]+=c[i-1];
+		_rep(i,1,cnt)topu[c[len[i]]--]=i;
+		if(opt)for(int i=cnt;i>1;i--)sz[fa[topu[i]]]+=sz[topu[i]];
+		else for(int i=cnt;i>1;i--)sz[i]=1;
+		sz[1]=0;
+		_rep(i,1,cnt)sum[i]=sz[i];
+		for(int i=cnt;i;i--){
+			_for(j,0,26)
+			sum[topu[i]]+=sum[ch[topu[i]][j]];
+		}
+		if(sum[1]<k)puts("-1");
+		else
+		dfs(1,k);
+	}
+}solver;
+char s[MAXN];
+int main()
+{
+	scanf("%s",s);
+	solver.init(s,strlen(s));
+	int t=read_int(),k=read_int();
+	solver.query(t,k);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具