差别

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

--- 2020-2021:teams:legal_string:王智彪:后缀自动机 [2021/07/29 00:27]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:后缀自动机 [2021/07/30 17:04] (当前版本)
王智彪
@@ 行 48: / 行 48: @@
 给 $SAM$ 赋予树形结构，树的根为 $0$ ，其余结点 $v$ 的父亲为 $link(v)$ 。则 $S_{1…p}$ 和 $S_{1…q}$ 的最长公共后缀对应的字符串就是 $v_{p}$ 和 $v_{q}$ 对应的 $LCA$ 的字符串。显然每个状态对应的子串种类数是 $len(i)-len(link(i))$ 。
+<hidden 算法实现>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int MAXN=1001000;
+struct NODE {
+	int ch[26];
+	int len,fa;
+	NODE() {
+		memset(ch,0,sizeof(ch));
+		len=0;fa=0;
+	}
+} dian[MAXN<<1];
+int las=1,tot=1;
+void add(int c) {
+	int p=las;
+	int np=las=++tot;
+	dian[np].len=dian[p].len+1;
+	for(; p&&!dian[p].ch[c]; p=dian[p].fa)dian[p].ch[c]=np;
+	if(!p)dian[np].fa=1;//以上为case 1
+	else {
+		int q=dian[p].ch[c];
+		if(dian[q].len==dian[p].len+1)dian[np].fa=q;//以上为case 2
+		else {
+			int nq=++tot;
+			dian[nq]=dian[q];
+			dian[nq].len=dian[p].len+1;
+			dian[q].fa=dian[np].fa=nq;
+			for(; p&&dian[p].ch[c]==q; p=dian[p].fa)dian[p].ch[c]=nq; //以上为case 3
+		}
+	}
+}
+char s[MAXN];
+int len;
+int main() {
+	scanf("%s",s);
+	len=strlen(s);
+	for(int i=0; i<len; i++)add(s[i]-'a');
+	return 0;
+}
+</code>
+</hidden>
+===== 算法练习 =====
+.给一个文本串 $T$ 和多个模式串 $P$ ，询问 $P$ 是否作为 $T$ 的一个子串出现。
+首先用 $O(|T|)$ 的时间对 $T$ 构造后缀自动机，从 $t_{0}$ 开始根据 $P$ 开始转移，如果在某个点无法转移下去，则不是子串，反之则出现过，为子串。时间复杂度为 $O(|P|)$ ，且可以求出 $P$ 在文本串中出现的最大前缀长度（其实后缀数组也可以做，连起来用字符分割，用 $O(n)$ 的算法构造，然后看那个位置 $rk$ 数组值加一位置的 $height$ 数组值，即为最长前缀长度）。
+.给一个字符串 $S$ ，计算不同子串的个数
+做法 $1$ ：后缀数组显然可以做，这里可以对 $S$ 构造后缀自动机，每一个 $S$ 的子串都对应自动机的路径，所以不同子串的个数等于自动机中以 $t_{0}$ 为起点的不同路径的条数。树形 $dp$ 的思想，我们设 $dp[v]$ 为状态 $v$ 开始的路径数量（包括空串），则可以有 $dp[v]=1+\sum_{(v,w,c)exists}dp[w]$ ，也就是说每一棵子树的所有情况都可以包括进来（包括空，因为有一条边这样肯定不是空串了），最后再加上自己的那个空串，所以最后加 $1$ ，所以最后不同字串的个数是 $dp[t_{0}]-1$ （把空串排除）。复杂度 $O(|S|)$ 。
+做法 $2$ ：每个结点对应的子串数量是 $len(i)-len(link(i))$ 对所有结点求和即可，复杂度也是 $O(|S|)$ 。
+.给定一个字符串 $S$ ，计算所有不同子串的总长度
+做法 $1$ ：对两个部分进行树形 $dp$ ，不同字串的数量 $dp[v]$ 和他们的总长度 $ans[v]$ ，上一问的做法我们把 $dp[v]$ 搞定之后， $ans[v]=\sum_{(v,w,c)exists}dp[w]+ans[w]$ （因为有多少个串，都会多一个长度，所以在原有的答案上再加上有多少个串就可以了）。复杂度仍然是 $O(|S|)$ 的。
+做法 $2$ ：同上一问，后缀长度连续，为 $len(i)$ 到 $len(link(i))+1$ ，所以等差数列求和，对所有顶点相加即可，复杂度同样是 $O(|S|)$ 的。
+.字典序第 $k$ 大子串。多组询问，每次询问 $k$ 。
+字典序第 $k$ 大对应着 $SAM$ 中第 $k$ 大的路径。我们计算完每一个儿子有多少个子串之后，从根开始找第一个和超过 $k$ 的位置，然后减去之前的那些，继续递归着找就可以了，复杂度大概是 $O(|\sum||ans|)$ ，其中 $|ans|$ 为查询的答案。显然后缀数组更加可做。
+.最小循环移位
+貌似不用后缀自动机也是 $O(n)$ 的。这里介绍后缀自动机的做法。
+需要倍增字符串（老套路），所以这个题变成了在 $S+S$ 的后缀自动机上，寻找最小的长度为 $|S|$ 的路径，这个路径代表的字符串一定是原来 $S$ 的子串，所以这样找到的子串一定是原来的最小循环移位。所以从初始状态 $t_{0}$ 开始，贪心地访问能访问的最小字符即可。
+<hidden 代码>
+<code cpp>
+void find() {
+	int tlas=1;
+	for(int i=0;i<len;i++) {
+		for(int j=0;j<26;j++) {
+			if(dian[tlas].ch[j]) {
+				tlas=dian[tlas].ch[j];
+				printf("%c",'a'+j);
+				break;
+			}
+		}
+	}
+}
+int main() {
+	scanf("%s",s);
+	len=strlen(s);
+	for(int i=0;i<len;i++) {
+		add(s[i]-'a');
+	}
+	for(int i=0;i<len;i++) {
+		add(s[i]-'a');
+	}
+	find();
+	return 0;
+}
+</code>
+</hidden>
+.给定一个文本串 $T$ ，多组询问，每次询问字符串 $P$ ，你需要回答 $P$ 在字符串 $T$ 中作为子串出现了多少次。
+将模式串沿着后缀自动机跑，跑不下去答案为 $0$ ，如果跑完，答案就是该节点的终点集合大小。
+预处理：对于自动机中的每个状态 $v$ ，处理 $cnt_{v}$ ，使之等于 $endpos(v)$ 集合的大小（也就是等价类中包含了多少个串）。显然这个值可以用后缀链接来算，后缀链接显然编号更小，于是为了保证计算加上的都是已经计算正确的，可以沿长度降序遍历， $cnt_{link(v)}+=cnt_{v}$ 。这里我们把每个状态，如果不是通过复制创建的且不是初始状态 $t_{0}$ ，我们就讲它的 $cnt$ 初始化为 $1$ 。（不是通过复制获得的状态，恰好有 $|T|$ 个，我们需要计算的是它们所对应位置的数量，所以他们的 $cnt$ 赋值为 $1$ ，其他的赋值为 $0$ ）。而 $cnt_{link(v)}+=cnt_{v}$ 的含义是，如果一个字符串 $v$ 出现了 $cnt_{v}$ 次，那么它的所有后缀也在这个位置结束，所以后缀链接那些字符串也在这里结束，所以需要加上 $cnt_{v}$ 次。所以我们用 $O(T)$ 的时间计算出了所有状态的 $cnt$ 值。
+所以每次询问只需要找到 $cnt_{t}$ ，也就是这个字符串代表的状态，所以单次时间复杂度为 $O(|P|)$ 。
+.给定一个文本串 $T$ ，多组查询，每次查询字符串 $P$ 在 $T$ 中第一次出现的位置（开头位置）。
+我们对于每个状态，需要预处理 $firstpos$ （第一次出现这个状态的末端位置，也就是每一个 $endpos$ 集合中最小的元素）。我们需要分情况讨论：
+当此状态是新创建的状态 $cur$ 时，我们令 $firstpos(cur)=len(cur)-1$ 。
+当此状态是结点 $q$ 复制到 $clone$ 时，我们令 $firstpos(clone)=firstpos(q)$ 。
+所以答案就是 $firstpos(t)-|P|+1$ ， $t$ 是 $P$ 末尾的状态，单次时间复杂度是 $O(|P|)$ 的。
+.查询模式串在文本串出现的所有位置
+和上一问类似，我们为所有状态计算位置 $firstpos$ ，设模式串为 $T$ ，在后缀自动机中对应状态为 $t$ ，显然 $firstpos(t)$ 是答案的一部分。我们显然需要找到所有可以通过后缀链接到达 $t$ 的状态。我们存一下每个状态的后缀引用列表，然后从 $t$ 结点 $dfs$ 下去，把所有状态的 $firstpos$ 值都输出就可以了。这个复杂度是 $O(ans(P))$ ，访问了多少个结点就是多少个答案，并且一个结点只会访问一次。但是这样子遇到复制出来的结点，他们的 $firstpos$ 是一样的，所以需要标记是否是复制出来的，如果是则不输出就可以了。
+<hidden 处理>
+<code cpp>
+struct NODE {
+	bool is_clone;
+	map<int,int> ch;
+	int len,fa,firstpos;
+	vector<int> vec;
+	NODE() {
+		ch.clear();
+		is_clone=len=fa=firstpos=0;
+		vec.clear();
+	}
+}dian[MAXN<<1];
+int add(int c,int id) {
+	int p=las;
+	int np=las=++tot;
+	dian[np].len=dian[p].len+1;
+	dian[np].firstpos=id;
+	for(; p&&!dian[p].ch[c]; p=dian[p].fa)dian[p].ch[c]=np;
+	if(!p)dian[np].fa=1;//以上为case 1
+	else {
+		int q=dian[p].ch[c];
+		if(dian[q].len==dian[p].len+1)dian[np].fa=q;//以上为case 2
+		else {
+			int nq=++tot;
+			dian[nq].is_clone=true;
+			dian[nq]=dian[q];
+			dian[nq].len=dian[p].len+1;
+			dian[q].fa=dian[np].fa=nq;
+			for(; p&&dian[p].ch[c]==q; p=dian[p].fa)dian[p].ch[c]=nq; //以上为case 3
+		}
+	}
+	return dian[las].len-dian[dian[las].fa].len;
+}
+void dfs(int now,int length) {
+	if(!dian[now].is_clone) printf("%d\n",dian[now].firstpos-length+1);
+	for(int i=0;i<dian[now].vec.size();i++) {
+		dfs(dian[now].vec[i],length);
+	}
+}
+//然后main函数里就是把这个字符串的终止位置找到，然后从终止位置开始dfs就可以了。
+</code>
+</hidden>
+.最长公共子串
+后缀数组基本操作。
+后缀自动机做法：对 $S$ 构造后缀自动机，处理字符串 $T$ ，对于每一个前缀，都在 $S$ 中寻找这个前缀的最长后缀。显然所有这样的答案取最大值就是最终的答案了。
+我们维护两个变量：当前状态 $v$ 和当前长度 $l$ 。最开始 $v=t_{0}$ 且 $l=0$ 。
+如果存在从 $v$ 到字符 $c$ 的转移，我们只需要转移并且让 $l++$ 。
+如果不存在只能让状态一直跳 $link$ ，并且缩短长度，赋值为当前状态的长度 $len(v)$ 即可。
+如果仍不存在，则必然到达 $-1$ ，这时我们重新让 $v=0,l=0$ 。
+这样我们最多移动两倍 $|T|$ ，所以时间复杂度就是 $O(|T|)$ 。
+<hidden 实现>
+<code cpp>
+void work_lcs(char s1[],char s2[]) {
+	ans=0,anspos=-1;
+	int l1=strlen(s1),l2=strlen(s2);
+	for(int i=0;i<l1;i++) {
+		add(s1[i]-'a',i+1);
+	}
+	int v=1,l=0;
+	for(int i=0;i<l2;i++) {
+		while(v!=1&&!dian[v].ch[s2[i]-'a']) {
+			v=dian[v].fa;
+			l=dian[v].len;
+		}
+		if(dian[v].ch[s2[i]-'a']) {
+			v=dian[v].ch[s2[i]-'a'];
+			l++;
+		}
+		if(l>ans) {
+			ans=l;
+			anspos=i;
+		}
+	}
+	//printf("%d %d\n",ans,anspos);
+	if(anspos==-1) {
+		puts("no lcs!");
+	}
+	else {
+		for(int i=anspos-ans+1;i<=anspos;i++) {
+			putchar(s2[i]);
+		}
+		putchar(10);
+	}
+}
+</code>
+</hidden>
+剩下在oi-wiki上的例题之后再补吧...

CVBB ACM Team

用户工具

站点工具

差别

页面工具