【NOIP2013模拟联考8】匹配(match) 题解

B 组都说看不懂……我也解释不清啊……只能写这么详细了

ac 自动机

ac 自动机上 dp

怎么才能判定一个母串是否包含几个模式串？

我们可以想到 ac 自动机，考虑对模式串建 ac 自动机，如果我们跑到了一个标记为 tail 的节点，说明我们的母串包含了这一个模式串。

所以我们设 \(f[i][s][j]\) 表示我们母串的长度为 \(i\)，模式串的匹配状态为 \(s\)（状压后），当前母串跑到了 ac 自动机的节点 \(j\)。

我们枚举母串的第 \(i+1\) 个字符为 \(c\)，然后在 ac 自动机上跑 \(j\) 的儿子 \(c\)，再判断是否被标记为 tail，如果是，则对模式串的匹配状态 \(s\) 进行修改。

然后记得需要跳 fail。

这些过程和 ac 自动机的匹配过程一模一样。

我们发现跳 fail 并不是线性的，所以我们需要优化它。

因为模式串很少，我们可以把跑到一个 fail 所有的模式串的 tail 状压起来。

我们在建 fail 树时 tail[u] |= tail[fail[u]] 即可。

#include <cstdio>
#include <queue>
using namespace std;
#define N 110
#define M 32
#define K 8
#define P 1000000007
int n, m, k, cnt, ans;
char s[M];
int can[M];
int f[2][1<<K][N*M];
int nxt[N*M][26];
int tail[N*M];
int fail[N*M];
bool vis[26];
void insert(int x) {
	int p = 0;
	for(int i = 1; s[i] != '\0'; i++) {
		if(!nxt[p][s[i]-'a']) {
			nxt[p][s[i]-'a'] = ++cnt;
		}
		p = nxt[p][s[i]-'a'];
	}
	tail[p] |= (1 << x);
}
void build() {
	queue<int> q;
	for(int i = 1; i <= m; i++) 
		if(nxt[0][can[i]]) q.push(nxt[0][can[i]]);
	while(!q.empty()) {
		int p = q.front();
		q.pop();
		tail[p] |= tail[fail[p]];
		for(int i = 1; i <= m; i++) {
			if(nxt[p][can[i]]) {
				fail[nxt[p][can[i]]] = nxt[fail[p]][can[i]];
				q.push(nxt[p][can[i]]);
			} else {
				nxt[p][can[i]] = nxt[fail[p]][can[i]];
			}
		}
	}
}
int main() {
	scanf("%d %d", &n, &k);
	for(int i = 0; i < k; i++) {
		scanf("%s", s+1);
		insert(i);
	}
	scanf("%d", &m);
	m = 0;
	scanf("%s", s+1);
	for(int i = 1; s[i] != '\0'; i++) {
		if(!vis[s[i]-'a']) {
			vis[s[i]-'a'] = 1;
			can[++m] = s[i]-'a';
		}
	}
	build();
	f[0][0][0] = 1;
	for(int i = 0; i < n; i++) {
		for(int s = 0; s < (1<<k); s++) {
			for(int p = 0; p <= cnt; p++) {
				f[(i+1) % 2][s][p] = 0;
			}
		}
		for(int s = 0; s < (1<<k); s++) {
			for(int p = 0; p <= cnt; p++) {
				if(!f[i%2][s][p]) continue;
				for(int j = 1; j <= m; j++) {
					int pp = nxt[p][can[j]];
					(f[(i+1) % 2][s | tail[pp]][pp] += f[i%2][s][p]) %= P;
				}
			}
		}
	}
	for(int i = 0; i <= cnt; i++) {
		(ans += f[n%2][(1<<k)-1][i]) %= P;
	}
	printf("%d", ans);
}