<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
某人读论文,一篇论文是由许多单词组成的。
但他发现一个单词会在论文中出现很多次,现在他想知道每个单词分别在论文中出现多少次。
输入格式
第一行一个整数 $N$,表示有多少个单词。
接下来 $N$ 行每行一个单词,单词中只包含小写字母。
输出格式
输出 $N$ 个整数,每个整数占一行,第 $i$ 行的数字表示第 $i$ 个单词在文章中出现了多少次。
数据范围
$1 \\le N \\le 200$,
所有单词长度的总和不超过 $10^6$。
输入样例:
3
a
aa
aaa
输出样例:
6
3
1
思路
不懂 $AC$ 自动机的请点 $AC$ 自动机详解{:target=”_blank”}
我们先分析一下,对于所有节点 $i$ ,都有 $f[fail[i]]\in f[i]$ ,这里的 $f[i]$ 表示从根节点到 $i$ 所组成的字符串的方案。(代码里是方案数)
还有一点,我们所有 $fail$ 指针组成的边一定是一个 $DAG$ ,因为所有的 $fail$ 指针只能指向比自己层数更高的点。所以我们可以根据拓扑序来倒推,而我们用的是手写队列,就可以直接倒着遍历队列。
代码
#include <iostream>
using namespace std;
const int N = 210,M = 1000010;
int n;
int tr[M][26],cnt[M],id[N],idx;
int fail[M],q[M];
int f[M];
void insert (char s[M],int x) {
int p = 0;
for (int i = 0;s[i];i++) {
int t = s[i] - 'a';
if (!tr[p][t]) tr[p][t] = ++idx;
p = tr[p][t];
f[p]++;
}
cnt[p]++;
id[x] = p;
}
void get_fail () {
int hh = 0,tt = -1;
for (int i = 0;i < 26;i++) {
if (tr[0][i]) q[++tt] = tr[0][i];
}
while (hh <= tt) {
int t = q[hh++];
for (int i = 0;i < 26;i++) {
int p = tr[t][i];
if (!p) tr[t][i] = tr[fail[t]][i];
else {
fail[p] = tr[fail[t]][i];
q[++tt] = p;
}
}
}
}
int main () {
scanf ("%d",&n);
for (int i = 1;i <= n;i++) {
char s[M];
scanf ("%s",s);
insert (s,i);
}
get_fail ();
for (int i = idx - 1;i >= 0;i--) f[fail[q[i]]] += f[q[i]]; //这里一共有idx个点,而队列是从0开始存的,所以要减1
for (int i = 1;i <= n;i++) printf ("%d\n",f[id[i]]);
return 0;
}
赞
hhh,我感觉你这个fail没什么必要啊,博主。因为其实这里的fail他就是一个回退的指针。也就是一个建立回退边的指针,这个和之前的是一样的啊。不就是ne数组吗
好像ac自动机默认定位前缀的数组就是fail。ne是y总自己的习惯
没有ne数组啊?
回退指针需要的,他还要更新 trie 图
👍🏻