Rockdu's Blog

题目背景

这是一道简单的AC自动机模板题。

用于检测正确性以及算法常数。

为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。

管理员提示：本题数据内有重复的单词，且重复单词应该计算多次，请各位注意

题目描述

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

输入输出格式

输入格式：

第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

输出格式：

一个数表示答案

输入输出样例

2
a
aa
aa

2

说明

subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1；

subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6；

省选前打板子，AC自动机简单向上递推可达。水水更健康~

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 2e6 + 5;

int node[maxn], vis[maxn], ans, n;
namespace AC {
	int trie[maxn][26], fail[maxn], cnt = 1;
	int insert(char * s) {
		int len = strlen(s), id, now = 1;
		for(register int i = 0; i < len; ++i) {
			id = s[i] - 'a';
			if(trie[now][id]) now = trie[now][id];
			else trie[now][id] = ++cnt, now = cnt;
		}
		return now;
	}
	void create() {
		queue<int > q; q.push(1);
		int now, p, v;
		while(!q.empty()) {
			now = q.front(); q.pop();
			for(register int i = 0; i < 26; ++i) {
				if(!trie[now][i]) continue;
				v = trie[now][i], p = fail[now];
				while(p && !trie[p][i]) p = fail[p];
				if(!p) fail[v] = 1;
				else fail[v] = trie[p][i];
				q.push(v);
			}
		}
	}
	void work(char * s) {
		int len = strlen(s), now = 1, id, p;
		for(register int i = 0; i < len; ++i) {
			id = s[i] - 'a', vis[now] = 1;
			while(now && !trie[now][id]) now = fail[now];
			if(now) now = trie[now][id]; else now = 1;
			p = fail[now]; while(p && !vis[p]) vis[p] = 1, p = fail[p];
		}
		vis[now] = 1;
	}
}

char s[maxn];

int main() {
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i)
		scanf("%s", s), node[i] = AC::insert(s);
	AC::create(), scanf("%s", s), AC::work(s);
	for(register int i = 1; i <= n; ++i)
		if(vis[node[i]]) ++ans;
	printf("%d", ans);
	return 0;
}