差别

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

--- 2020-2021:teams:legal_string:jxm2001:字符串_2 [2020/08/29 18:04]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:字符串_2 [2020/10/01 20:08] (当前版本)
jxm2001 [算法例题]
@@ 行 346: / 行 346: @@
 </hidden>
+=== 例题四 ===
+[[https://www.luogu.com.cn/problem/P4052|洛谷p4052]]
+== 题意 ==
+给定 $n$ 个模式串 $S_i$，问有多少个长度为 $m$ 的文本串至少包含一个模式串。(模式串、文本串只含大写字母)
+== 题解 ==
+考虑计算出不含任何模式串的文本串，再用总数减去该值即可得到答案。
+接下来标记所有模式串终止位置在 $\text{fail}$ 树上的子节点，显然转移时不能到达标记结点。
+最后设 $\text{dp}(i,j)$ 表示当前位于结点 $i$ 且长度为 $j$ 的方案数，暴力转移即可。总时空间复杂度 $O(m\sum_{i=1}^n |S_i|)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXL=105,MAXS=6005,Mod=1e4+7;
+int quick_pow(int a,int b){
+	int ans=1;
+	while(b){
+		if(b&1)ans=ans*a%Mod;
+		a=a*a%Mod;
+		b>>=1;
+	}
+	return ans;
+}
+struct AC{
+	int ch[MAXS][26],val[MAXS],fail[MAXS],sz;
+	int dp[MAXS][MAXL];
+	void insert(char *s){
+		int len=strlen(s),pos=0;
+		_for(i,0,len){
+			int c=s[i]-'A';
+			if(!ch[pos][c])
+			ch[pos][c]=++sz;
+			pos=ch[pos][c];
+		}
+		val[pos]=1;
+	}
+	void getFail(){
+		queue<int> q;
+		_for(i,0,26){
+			if(ch[0][i])
+			q.push(ch[0][i]);
+		}
+		while(!q.empty()){
+			int u=q.front();q.pop();
+			_for(i,0,26){
+				if(ch[u][i]){
+					fail[ch[u][i]]=ch[fail[u]][i];
+					val[ch[u][i]]|=val[ch[fail[u]][i]];
+					q.push(ch[u][i]);
+				}
+				else ch[u][i]=ch[fail[u]][i];
+			}
+		}
+	}
+	int query(int n){
+		dp[0][0]=1;
+		_for(i,0,n){
+			_rep(j,0,sz){
+				_for(k,0,26){
+					if(val[ch[j][k]])continue;
+					dp[ch[j][k]][i+1]+=dp[j][i];
+					dp[ch[j][k]][i+1]%=Mod;
+				}
+			}
+		}
+		int ans=0;
+		_rep(i,0,sz)ans=(ans+dp[i][n])%Mod;
+		return ans;
+	}
+}solver;
+char buf[MAXL];
+int main()
+{
+	int n=read_int(),m=read_int();
+	_rep(i,1,n){
+		scanf("%s",buf);
+		solver.insert(buf);
+	}
+	solver.getFail();
+	int del=solver.query(m);
+	enter((quick_pow(26,m)-del+Mod)%Mod);
+	return 0;
+}
+</code>
+</hidden>
+=== 例题五 ===
+[[https://ac.nowcoder.com/acm/contest/7009/F|NC210775]]
+== 题意 ==
+给定 $n$ 个模式串，每个字符串有一个权值 $v$。要求构造一个长度为 $L$ 的字符串，使得其包含的模式串权值和最大。(包含多个相同模式串结果将累加)
+== 题解 ==
+标记所有模式串终止位置在 $\text{fail}$ 树上的子节点，子树可以累加父节点的权值。
+最后设 $\text{dp}(i,j)$ 表示当前位于结点 $i$ 且长度为 $j$ 的最大答案，暴力转移。总时空间复杂度 $O(L\sum_{i=1}^n |S_i|)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXL=1e3+5,MAXS=2005,Inf=1e9;
+struct AC{
+	int ch[MAXS][26],val[MAXS],fail[MAXS],sz;
+	int dp[MAXS][MAXL];
+	void insert(char *s,int v){
+		int len=strlen(s),pos=0;
+		_for(i,0,len){
+			int c=s[i]-'a';
+			if(!ch[pos][c])
+			ch[pos][c]=++sz;
+			pos=ch[pos][c];
+		}
+		val[pos]+=v;
+	}
+	void getFail(){
+		queue<int> q;
+		_for(i,0,26){
+			if(ch[0][i])
+			q.push(ch[0][i]);
+		}
+		while(!q.empty()){
+			int u=q.front();q.pop();
+			val[u]+=val[fail[u]];
+			_for(i,0,26){
+				if(ch[u][i]){
+					fail[ch[u][i]]=ch[fail[u]][i];
+					q.push(ch[u][i]);
+				}
+				else ch[u][i]=ch[fail[u]][i];
+			}
+		}
+	}
+	int query(int n){
+		_rep(i,0,n)_rep(j,0,sz)dp[j][i]=-Inf;
+		dp[0][0]=0;
+		_for(i,0,n){
+			_rep(j,0,sz){
+				if(dp[j][i]==-Inf)continue;
+				_for(k,0,26)
+				dp[ch[j][k]][i+1]=max(dp[ch[j][k]][i+1],dp[j][i]+val[ch[j][k]]);
+			}
+		}
+		int ans=-Inf;
+		_rep(i,0,sz)
+		ans=max(ans,dp[i][n]);
+		return ans;
+	}
+}solver;
+char buf[MAXS];
+int main()
+{
+	int n,m;
+	cin>>n>>m;
+	_rep(i,1,n){
+		scanf("%s",buf);
+		int v;
+		cin>>v;
+		solver.insert(buf,v);
+	}
+	solver.getFail();
+	enter(solver.query(m));
+	return 0;
+}
+</code>
+</hidden>
+=== 例题六 ===
+[[https://ac.nowcoder.com/acm/contest/7817/G|2020牛客国庆集训派对day1 G题]]
+== 题意 ==
+给定 $m$ 个禁止串 $S_i$，求长度为 $n$ 且子串不含任意禁止串的字符串数。
+数据保证 $\sum_{i=1}^m |S_i|\le 100,n\le 10^9$。
+== 题解 ==
+考虑建立 $\text{fail}$ 树，然后标记所有禁止串终止结点以及其在 $\text{fail}$ 树中的子树。
+然后将树边转化为 $\sum_{i=1}^m |S_i|\times \sum_{i=1}^m |S_i|$ 的邻接矩阵 $A$ 来进行状态转移，套用矩阵快速幂即可快速求解，最后答案即为 $\sum A_{0,i}$。
+时间复杂度 $O\left((\sum_{i=1}^m |S_i|)^3\log n\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXS=105,Mod=1e9+7;
+struct Matrix{
+	int ele[MAXS][MAXS];
+	Matrix operator * (const Matrix &b){
+		Matrix c;
+		mem(c.ele,0);
+		_for(i,0,MAXS)
+		_for(j,0,MAXS)
+		_for(k,0,MAXS)
+		c.ele[i][j]=(c.ele[i][j]+1LL*ele[i][k]*b.ele[k][j])%Mod;
+		return c;
+	}
+};
+Matrix quick_pow(Matrix a,int n){
+	Matrix ans;
+	mem(ans.ele,0);
+	_for(i,0,MAXS)
+	ans.ele[i][i]=1;
+	while(n){
+		if(n&1)
+		ans=ans*a;
+		a=a*a;
+		n>>=1;
+	}
+	return ans;
+}
+namespace AC{
+	int ch[MAXS][26],val[MAXS],fail[MAXS],sz;
+	void insert(char *s){
+		int len=strlen(s),pos=0;
+		_for(i,0,len){
+			int c=s[i]-'a';
+			if(!ch[pos][c])
+			ch[pos][c]=++sz;
+			pos=ch[pos][c];
+		}
+		val[pos]=1;
+	}
+	int getAns(int n){
+		queue<int>q;
+		_for(i,0,26){
+			if(ch[0][i])
+			q.push(ch[0][i]);
+		}
+		while(!q.empty()){
+			int u=q.front();q.pop();
+			_for(i,0,26){
+				if(ch[u][i]){
+					fail[ch[u][i]]=ch[fail[u]][i];
+					val[ch[u][i]]|=val[ch[fail[u]][i]];
+					q.push(ch[u][i]);
+				}
+				else
+				ch[u][i]=ch[fail[u]][i];
+			}
+		}
+		Matrix a;
+		_rep(i,0,sz){
+			_rep(j,0,sz)
+			a.ele[i][j]=0;
+			_for(j,0,26){
+				if(!val[ch[i][j]])
+				a.ele[i][ch[i][j]]++;
+			}
+		}
+		a=quick_pow(a,n);
+		int ans=0;
+		_rep(i,0,sz)
+		ans=(ans+a.ele[0][i])%Mod;
+		return ans;
+	}
+}
+char s[MAXS];
+int main()
+{
+	int n=read_int(),m=read_int();
+	while(m--){
+		int len=read_int();
+		scanf("%s",s);
+		AC::insert(s);
+	}
+	enter(AC::getAns(n));
+	return 0;
+}
+</code>
+</hidden>
+=== 例题七 ===
+[[https://www.luogu.com.cn/problem/UVA11019|UVA11019]]
+== 题意 ==
+给定一个 $n\times m$ 的二维文本串和一个 $x\times y$ 的二维模式串，问模式串在文本串中的出现次数。
+== 题解 ==
+考虑将模式串按行拆分为 $t_1,t_2\cdots t_x$ 后插入 $\text{AC}$ 自动机，同时进行编号(相同的字符串共用一个编号)。
+再将 $t_1,t_2\cdots t_x$ 的编号相连得到一个一维数组 $b$。
+同时将文本串按行拆分为 $s_1,s_2\cdots s_n$ 后在 $\text{AC}$ 自动机查询并记录匹配位置的模式串编号，得到一个二维数组 $a$。
+二维数组中元素 $a_{i,j}$ 的意义是 $s[i][j-y+1,j]$ 与模式串 $t_{a_{i,j}}$ 匹配。
+于是对 $a$ 的每列跑 $\text{KMP}$ 算法记录 $b$ 的出现数即可。时间复杂度 $O(nm+xy)$。
+注意上述方法中 $AC$ 自动机起到了降维的作用，且可以拓展到任意维字符串匹配。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e3+5,MAXS=1e4+5;
+namespace KMP{
+	int f[MAXN];
+	int find(int *s1,int n,int *s2,int m){
+		int pos=0,cnt=0;
+		f[1]=0;
+		_rep(i,2,m){
+			while(pos&&s2[i]!=s2[pos+1])pos=f[pos];
+			if(s2[i]==s2[pos+1])pos++;
+			f[i]=pos;
+		}
+		pos=0;
+		_rep(i,1,n){
+			while(pos&&s1[i]!=s2[pos+1])pos=f[pos];
+			if(s1[i]==s2[pos+1])pos++;
+			if(pos==m){
+				cnt++;
+				pos=f[pos];
+			}
+		}
+		return cnt;
+	}
+}
+struct AC{
+	int ch[MAXS][26],val[MAXS],fail[MAXS],sz,cnt;
+	void clear(){
+		sz=cnt=0;
+		mem(ch[0],0);
+	}
+	int insert(char *s){
+		int len=strlen(s),pos=0;
+		_for(i,0,len){
+			int c=s[i]-'a';
+			if(!ch[pos][c]){
+				ch[pos][c]=++sz;
+				mem(ch[sz],0);
+				val[sz]=fail[sz]=0;
+			}
+			pos=ch[pos][c];
+		}
+		if(val[pos])return val[pos];
+		return val[pos]=++cnt;
+	}
+	void getFail(){
+		queue<int> q;
+		_for(i,0,26){
+			if(ch[0][i])
+			q.push(ch[0][i]);
+		}
+		while(!q.empty()){
+			int u=q.front();q.pop();
+			val[u]+=val[fail[u]];
+			_for(i,0,26){
+				if(ch[u][i]){
+					fail[ch[u][i]]=ch[fail[u]][i];
+					q.push(ch[u][i]);
+				}
+				else ch[u][i]=ch[fail[u]][i];
+			}
+		}
+	}
+	void query(char *s,int *ans,int n){
+		int pos=0;
+		_for(i,0,n){
+			pos=ch[pos][s[i]-'a'];
+			ans[i]=val[pos];
+		}
+	}
+}solver;
+char s1[MAXN][MAXN],s2[MAXN];
+int a[MAXN][MAXN],b[MAXN],c[MAXN];
+int main()
+{
+	int T=read_int();
+	while(T--){
+		solver.clear();
+		int n=read_int(),m=read_int(),ans=0;
+		_rep(i,1,n)scanf("%s",s1[i]);
+		int x=read_int(),y=read_int();
+		_rep(i,1,x){
+			scanf("%s",s2);
+			b[i]=solver.insert(s2);
+		}
+		solver.getFail();
+		_rep(i,1,n)
+		solver.query(s1[i],a[i],m);
+		_for(i,y-1,m){
+			_rep(j,1,n)c[j]=a[j][i];
+			ans+=KMP::find(c,n,b,x);
+		}
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具