洛谷P3966 [TJOI2013]单词(AC自动机)
洛谷P3966 [TJOI2013]单词(AC自动机)
attack
发布于 2018-07-04 12:26:09
发布于 2018-07-04 12:26:09
题目描述
小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成但小张发现一个单词会在论文中出现很多次,他想知道每个单词分别在论文中出现了多少次。
输入输出格式
输入格式：
第一行一个整数N,表示有N个单词。接下来N行每行一个单词,每个单词都由小写字母(a-z)组成。(N≤200)
输出格式：
输出N个整数,第i行的数表示第i个单词在文章中出现了多少次。
输入输出样例
输入样例#1： 复制
3
a
aa
aaa输出样例#1： 复制
6
3
1说明
数据范围
30%的数据， 单词总长度不超过10^3
100%的数据，单词总长度不超过10^6
自己xjb YY了一个做法居然1Ahhh
首先应该一眼就能看出是AC自动机。
那么我们先把所有串的AC自动机搞出来，然后记录下他们拼起来的串，用随便一个字符分隔
暴力枚举每一个串，把经过的路径上的权值$+1$，表示该位置代表的串又多出现了一次。
这样我们就统计出了与它一模一样的串的出现次数。
还有一种情况，即当它作为某些串的后缀出现。
此时，根据AC自动机的性质不难发现，我们要求的答案即为该节点在$fail$树上子树的和
然后直接暴力把$fail$树建出来，树形DP统计答案即可
就是跑的有点慢
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 1e6 + 100, B = 28;
int T;
char s[MAXN], a[MAXN];
int fail[MAXN], ch[MAXN][28], val[MAXN], tot = 0, root = 0;
void insert(char *s) {
int N = strlen(s + 1);
int now = root;
for(int i = 1; i <= N; i++) {
int x = s[i] - 'a';
if(!ch[now][x]) ch[now][x] = ++tot;
now = ch[now][x];
val[now]++;
}
}
vector<int> v[MAXN];
void GetFail() {
queue<int> q;
for(int i = 0; i < B; i++) if(ch[root][i]) q.push(ch[root][i]);
while(!q.empty()) {
int p = q.front(); q.pop();
for(int i = 0; i < B; i++) {
if(ch[p][i]) fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]);
else ch[p][i] = ch[fail[p]][i];
}
v[fail[p]].push_back(p);
}
}
void GetVal(int x) {
for(int i = 0; i < v[x].size(); i++)
GetVal(v[x][i]), val[x] += val[v[x][i]];
}
void GetAns(char *s) {
int N = strlen(s + 1), now = root, ans = 0;
for(int i = 1; i <= N; i++) {
int x = s[i] - 'a';
if(x == 26) printf("%d\n", val[now]), now = root, ans = 0;
now = ch[now][x];
}
printf("%d", val[now]);
}
int main() {
//freopen("a.in", "r", stdin);
scanf("%d", &T);
for(int i = 1; i <= T; i++) {
scanf("%s", s + 1);
insert(s);
s[0] = 'z' + 1;
strcat(a, s);
}
GetFail();
GetVal(0);
GetAns(a);
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-06-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录