这是一道简单的AC自动机模板题。
用于检测正确性以及算法常数。
为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。
管理员提示:本题数据内有重复的单词,且重复单词应该计算多次,请各位注意
给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。
输入格式:
第一行一个n,表示模式串个数;
下面n行每行一个模式串;
下面一行一个文本串。
输出格式:
一个数表示答案
输入样例#1: 复制
2
a
aa
aa
输出样例#1: 复制
2
subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1;
subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6;
感觉AC自动机比后缀自动机好理解多了qwq
就是把匹配串的trie树建出来然后跑一下匹配
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 1e6 + 10;
char s[MAXN];
int N;
int ch[MAXN][26], fail[MAXN], val[MAXN], tot = 0, root = 0;
void insert(char *s) {
int len = strlen(s + 1), now = root;
for(int i = 1; i <= len; i++) {
int x = s[i] - 'a';
if(!ch[now][x]) ch[now][x] = ++tot;
now = ch[now][x];
}
val[now]++;
}
void GetFail() {
queue<int> q;
for(int i = 0; i <= 25; i++)
if(ch[root][i]) q.push(ch[root][i]);
while(!q.empty()) {
int p = q.front(); q.pop();
for(int i = 0; i <= 25; i++) {
if(!ch[p][i]) ch[p][i] = ch[fail[p]][i];
else fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]);
}
}
}
int Find(char *s) {
int len = strlen(s + 1);
int now = root, ans = 0;
for(int i = 1; i <= len; i++) {
int x = s[i] - 'a';
now = ch[now][x];
for(int t = now; t && ~val[t]; t = fail[t]) ans += val[t], val[t] = -1;
}
return ans;
}
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
scanf("%d", &N);
for(int i = 1; i <= N; i++) {
scanf("%s", s + 1);
insert(s);
}
GetFail();
scanf("%s", s + 1);
printf("%d", Find(s));
return 0;
}