Codechef 13.8 LYRC AC自动机
题目大意：
给定$W$个单词，每个单词长度不超过$|P|$，另有$N$句长度不超过$|S|$的歌词，问每个单词在所有歌词中一共出现的次数。
数据范围：单词和歌词包含大小写英文字母、数字和横杠，$W\leq{500},|P|\leq{1000},N\leq{100},|S|\leq{50000}$。
算法讨论：
直接利用AC自动机进行处理，对单词建出AC自动机，对于每句歌词在AC自动机上走，每走到一个节点都相当于要在这个节点在Fail树上到根节点的路径上都+1，我们可以通过在这个节点上打一个标记来实现，最后再DFS一遍Fail树就能得到答案了。
时空复杂度：
时间复杂度$O(W|P|+N|S|)$，空间复杂度$O(63W|P|)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define L 500010
int tr[L][63], cnt;
int change(char c) {
if (c >= 'a' && c <= 'z')
return c - 'a';
if (c >= 'A' && c <= 'Z')
return c - 'A' + 26;
if (c >= '0' && c <= '9')
return c - '0' + 52;
return 62;
}
char s[50010];
vector<int> label[L];
queue<int> q;
int fail[L];
int head[L], nxt[L], to[L];
void addedge(int a, int b) {
static int q = 1;
to[q] = b;
nxt[q] = head[a];
head[a] = q++;
}
int c[L];
void dfs(int x) {
for (int j = head[x]; j; j = nxt[j]) {
dfs(to[j]);
c[x] += c[to[j]];
}
}
int ans[510];
int seq[L], fr, ta;
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
int n, i, j, k, len, p, y;
cin >> n;
gets(s);
for (i = 1; i <= n; ++i) {
gets(s);
len = strlen(s);
p = 0;
for (j = 0; j < len; ++j) {
y = change(s[j]);
if (!tr[p][y])
tr[p][y] = ++cnt;
p = tr[p][y];
}
label[p].push_back(i);
}
for (j = 0; j < 63; ++j)
if (tr[0][j])
q.push(tr[0][j]);
int u, v, r;
while (!q.empty()) {
u = q.front();
q.pop();
for (j = 0; j < 63; ++j) {
if ((v = tr[u][j])) {
q.push(v);
for (r = fail[u]; r && !tr[r][j]; r = fail[r]);
fail[v] = tr[r][j];
}
}
}
for (i = 1; i <= cnt; ++i)
addedge(fail[i], i);
int q;
cin >> q;
gets(s);
while (q--) {
gets(s);
len = strlen(s);
p = 0;
for (j = 0; j < len; ++j) {
y = change(s[j]);
while (p && !tr[p][y])
p = fail[p];
++c[p = tr[p][y]];
}
}
seq[ta++] = 0;
while (fr != ta) {
u = seq[fr++];
for (j = head[u]; j; j = nxt[j])
seq[ta++] = to[j];
}
for (i = ta - 1; i >= 0; --i)
c[fail[seq[i]]] += c[seq[i]];
for (i = 1; i <= cnt; ++i)
for (j = 0; j < (int)label[i].size(); ++j)
ans[label[i][j]] = c[i];
for (i = 1; i <= n; ++i)
printf("%d\n", ans[i]);
return 0;
}
评论 (0)