差别

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

--- 2020-2021:teams:legal_string:王智彪:后缀自动机 [2021/07/30 15:35]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:后缀自动机 [2021/07/30 17:04] (当前版本)
王智彪
@@ 行 165: / 行 165: @@
 所以每次询问只需要找到 $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

用户工具

站点工具

差别

页面工具