差别

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

--- 2020-2021:teams:legal_string:王智彪:序列自动机 [2021/08/01 01:13]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:序列自动机 [2021/08/01 19:25] (当前版本)
王智彪
@@ 行 16: / 行 16: @@
 构建复杂度是 $O(n|\sum|)$ 。
+===== 算法实现 =====
+==== 构造 ====
+<hidden 构造>
+<code cpp>
+struct SQAM {
+	int ch[MAXL][MAXM],las[MAXM];
+	int root;
+	void init() {
+		root=1;//构造根节点
+	}
+	void work(char s[]) {
+		int len=strlen(s);
+		for(int i=len-1;i>=0;i--) {
+			for(int j=0;j<MAXM;j++) ch[i+2][j]=las[j];//每个字符是一个节点 根节点是1 所以0位置字符状态为2
+			las[s[i]-'a']=i+2;
+		}
+		for(int i=0;i<MAXM;i++) ch[root][i]=las[i];
+	}
+}s1,s2;
+</code>
+</hidden>
+===== 代码练习 =====
 问题导入：
@@ 行 21: / 行 51: @@
 给定一个字符串 $S$ ， $q$ 次询问，每次给定另一个字符串 $T$ ，询问 $T$ 是否是 $S$ 的子序列。 $len(S)≤10^{5},q≤10^{5},\sum len(T)≤10^{6}$
-最暴力的做法：建一个 $t_{0}$ ，指向所有点，然后每个点的后继是后面的点，最后每个点打结束标记，这样光建边就要 $O(len^{2})$ 再加上查询是 $O(\sum |T|)$ 。显然爆炸。显然对于相同的字符贪心取前面的就好了，记录每种字符在哪些位置出现过。这个复杂度是 $O(len)$ 的，然后对于查找串的当前字符 $upper_bound(pos[c].begin(),pos[c].end(),now\_pos);$ ，如果查找到 $end$ 说明不存在，如果一直找到最后说明存在。这个的复杂度是 $O(|S|+\sum |T|*log(|S|))$ 的。
+最暴力的做法：建一个 $t_{0}$ ，指向所有点，然后每个点的后继是后面的点，最后每个点打结束标记，这样光建边就要 $O(len^{2})$ 再加上查询是 $O(\sum |T|)$ 。显然爆炸。显然对于相同的字符贪心取前面的就好了，记录每种字符在哪些位置出现过。这个复杂度是 $O(len)$ 的，然后对于查找串的当前字符 $upper_bound(pos[c].begin(),pos[c].end(),now_pos);$ ，如果查找到 $end$ 说明不存在，如果一直找到最后说明存在。这个的复杂度是 $O(|S|+\sum |T|*log(|S|))$ 的。
 <hidden 实现>
@@ 行 68: / 行 98: @@
 如果要支持带修，把 $vector$ 换成平衡树即可（修改变成 $O(logn)$ 的）。
+<hidden 带修代码>
+<code cpp>
+#include<iostream>
+#include<cstdlib>
+using namespace std;
+const int N=1e5+10;
+struct fhq_treap{
+	int lson,rson;
+	int val,key;
+	int size;
+};
+fhq_treap fhq[N];
+int root[N],a[N];
+int tot;
+inline int newnode(int val){
+	tot++;
+	fhq[tot].key=rand();
+	fhq[tot].val=val;
+	fhq[tot].size=1;
+	return tot;
+}
+inline void pushup(int pos){
+	fhq[pos].size=fhq[fhq[pos].lson].size+fhq[fhq[pos].rson].size+1;
+}
+void split(int pos,int val,int &x,int &y){
+	if(!pos){
+		x=y=0;
+		return ;
+	}
+	if(fhq[pos].val<=val){
+		x=pos;
+		split(fhq[pos].rson,val,fhq[x].rson,y);
+	}
+	else{
+		y=pos;
+		split(fhq[pos].lson,val,x,fhq[y].lson);
+	}
+	pushup(pos);
+}
+int merge(int x,int y){
+	if(!x||!y)
+		return x+y;
+	if(fhq[x].key<fhq[y].key){
+		fhq[x].rson=merge(fhq[x].rson,y);
+		pushup(x);
+		return x;
+	}
+	else{
+		fhq[y].lson=merge(x,fhq[y].lson);
+		pushup(y);
+		return y;
+	}
+}
+void ins(int &pos,int val){
+	int x,y;
+	split(pos,val,x,y);
+	pos=merge(merge(x,newnode(val)),y);
+}
+void del(int &pos,int val){
+	int x,y,z;
+	split(pos,val-1,x,y);
+	split(y,val,y,z);
+	y=merge(fhq[y].lson,fhq[y].rson);
+	pos=merge(merge(x,y),z);
+}
+int get_suc(int &pos,int val){
+	int x,y;
+	split(pos,val,x,y);
+	int ans=y;
+	while(fhq[ans].lson)
+		ans=fhq[ans].lson;
+	pos=merge(x,y);
+	return fhq[ans].val;
+}
+int main(){
+	int t,n,m,k;
+	cin>>t>>n>>m>>k;
+	for(int i=1;i<=n;i++){
+		cin>>a[i];
+		root[a[i]]=merge(root[a[i]],newnode(i));
+	}
+	int opt;
+	int x,y;
+	int pos=0;
+	bool flag;
+	for(int i=1;i<=m;i++){
+		cin>>opt;
+		if(opt){
+			cin>>x;
+			pos=0;
+			flag=true;
+			for(int j=1;j<=x;j++){
+				cin>>y;
+				pos=get_suc(root[y],pos);
+				if(!pos)
+					flag=false;
+			}
+			if(flag)
+				cout<<"Yes\n";
+			else
+				cout<<"No\n";
+		}
+		else{
+			cin>>x>>y;
+			del(root[a[x]],x);//删除
+			a[x]=y;//修改
+			ins(root[a[x]],x);//插入
+		}
+	}
+}
+</code>
+</hidden>
+.[[https://www.luogu.com.cn/problem/P4112#submit]]
+==== 题意 ====
+给定两个长度不超过 $2000$ 的字符串，分别设为 $s_{1},s_{2}$
+分为四个问题：
+  - 求 $s_{1}$ 的最短的子串且不是 $s_{2}$ 的子串
+  - 求 $s_{1}$ 的最短的子串且不是 $s_{2}$ 的子序列
+  - 求 $s_{1}$ 的最短的子序列且不是 $s_{2}$ 的子串
+  - 求 $s_{1}$ 的最短的子序列且不是 $s_{2}$ 的子序列
+如果没找到输出 $-1$ 。
+==== 题解 ====
+显然要分别对两个串建立后缀自动机和序列自动机
+因为要找最短的，所以 $BFS$ 开始搜，不管是什么自动机，从根节点往下开始搜，搜到 $s_{1}$ 有结点且 $s_{2}$ 没有的结点就可以了，如果到最后都没找到输出 $-1$ 即可。
+<hidden 代码>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+const int MAXL=2021;
+const int MAXM=46;
+const int MAXN=2021;
+struct SAM {
+	int las,tot;
+	struct NODE {
+		int ch[MAXM];
+		int len,fa;
+		NODE() {
+			memset(ch,0,sizeof(ch));
+			len=0;
+			fa=0;
+		}
+	} dian[MAXN<<1];
+	void init() {
+		las=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
+			}
+		}
+	}
+}S1,S2;
+char A[MAXL],B[MAXL];
+int la,lb;
+struct SQAM {
+	int ch[MAXL][MAXM],las[MAXM];
+	int root;
+	void init() {
+		root=1;//构造根节点
+	}
+	void work(char s[]) {
+		int len=strlen(s);
+		for(int i=len-1;i>=0;i--) {
+			for(int j=0;j<MAXM;j++) ch[i+2][j]=las[j];//每个字符是一个节点 根节点是1 所以0位置字符状态为2
+			las[s[i]-'a']=i+2;
+		}
+		for(int i=0;i<MAXM;i++) ch[root][i]=las[i];
+	}
+}s1,s2;
+struct Node {
+	int a,b,s;
+};
+int vis[MAXL<<1][MAXL<<1];
+int BFS(int v){
+	queue<Node>q;
+	vis[1][1]=v;
+	Node ntmp;
+	ntmp.a=1,ntmp.b=1,ntmp.s=0;
+	q.push(ntmp);
+	while(!q.empty()) {
+		ntmp=q.front();
+		int a=ntmp.a,b=ntmp.b,s=ntmp.s;
+		//printf("%d %d %d %d\n",a,b,s,v);
+		q.pop();
+		for(int i=0,da,db;i<MAXM;i++) {
+			if(v==1) {
+				da=S1.dian[a].ch[i],db=S2.dian[b].ch[i];
+			}else if(v==2) {
+				da=S1.dian[a].ch[i],db=s2.ch[b][i];
+			}else if(v==3) {
+				da=s1.ch[a][i],db=S2.dian[b].ch[i];
+			}else if(v==4) {
+				da=s1.ch[a][i],db=s2.ch[b][i];
+			}
+			//printf("%d %d %d\n",da,db,v);
+			if(vis[da][db]==v) continue;
+			if(da&&!db) return s+1;
+			if(da&&db) {
+				Node nntmp;
+				nntmp.a=da,nntmp.b=db,nntmp.s=s+1;
+				q.push(nntmp);
+				vis[da][db]=v;
+			}
+		}
+	}
+	return -1;
+}
+int main() {
+	scanf("%s%s",A,B);
+	la=strlen(A); lb=strlen(B);
+	s1.init();s2.init();S1.init();S2.init();
+	for(int i=0; i<la; i++) {
+		S1.add(A[i]-'a');
+	}
+	s1.work(A);
+	for(int i=0; i<lb; i++) {
+		S2.add(B[i]-'a');
+	}
+	s2.work(B);
+	int a1=BFS(1),a2=BFS(2),a3=BFS(3),a4=BFS(4);
+	printf("%d\n%d\n%d\n%d\n",a1,a2,a3,a4);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具