题解[ [JSOI2007]文本生成器 ]

题目

Link

给定(n)个模式串，求长度为(m)且不含模式串的文本串个数。

Sol

学习AC自动机的时候刷到了这道题.

看网上的各种题解，发现这类AC自动机上DP都是一种类似的套路。

首先，设(f[i][j])表示匹配到长度为(i)的地方，匹配到AC自动机上的第(j)个节点且不含模式串的方案数。

由于我们正向算方案容易算重，所以考虑求不含模式串的文本串数量。

设辅助数组(sz[id])表示在AC自动机上的第(id)个节点之前是否已经含有至少一个模式串。

设(nx[i][j])表示AC自动机上第(i)个节点，且下一个字符为(j)的后继节点。

那么：

[if(!sz[j][k]) f[i][nx[j][k]]+=f[i-1][j] ]

枚举一下就好了。

Code

#include<bits/stdc++.h>
#define N (61)
#define M (10010)
using namespace std;
const int P=10007;
int n,m,f[110][M];
char ss[M];
inline int read(){
	int w=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9'){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w;
}
struct Aho_C{
	int tot,nx[M][26],sz[M],fail[M];
	inline void insert(){
		scanf("%s",ss);
		int pos=0;
		for(int i=0;i<(int)strlen(ss);i++){
			if(!nx[pos][ss[i]-'A']) nx[pos][ss[i]-'A']=++tot;
			pos=nx[pos][ss[i]-'A'];
		}
		sz[pos]|=1;
		return;
	}
	inline void build(){
		queue<int>q;
		for(int i=0;i<26;i++) if(nx[0][i]) q.push(nx[0][i]);
		while(!q.empty()){
			int pos=q.front();
			q.pop();
			for(int i=0;i<26;i++){
				if(nx[pos][i]){
					sz[nx[pos][i]]|=sz[nx[fail[pos]][i]];
					fail[nx[pos][i]]=nx[fail[pos]][i];
					q.push(nx[pos][i]);
				}
				else nx[pos][i]=nx[fail[pos]][i];
			}
		}
		return;
	}
	inline void DP(){
		int ans=0,res=1;		
		f[0][0]=1;
		for(int i=1;i<=m;i++)
			for(int j=0;j<=tot;j++)
				for(int k=0;k<26;k++)
					if(!sz[nx[j][k]]) f[i][nx[j][k]]=(f[i][nx[j][k]]+f[i-1][j])%P;
		for(int i=0;i<=tot;i++) ans=(ans+f[m][i])%P;		
		for(int i=1;i<=m;i++) res=res*26%P;
		printf("%d
",(res-ans+P)%P);
		return;
	}
}AC;
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) AC.insert();
	AC.build();
	AC.DP();
	return 0;
}

完结撒花❀