目的:
1.求每个单词在字符串中出现的总次数
思路:
1.首先,自身算一次。
2.我们查找当前单词在别的单词中间出现多少次,以后缀形式查找。
3.举例:我们在abcd中找bc,我们是在trie树中,通过a-b-c形式的c连接到的结点来判断的。
4.以c为末尾的字符串的next转移到的最长前缀,不一定包含我们需要的后缀。
5.因为我们只能确定最后一个字符是什么,但是我们需要的后缀的末尾字符一定是c。
操作:
1.建立trie树插入的时候,每个结点都要cnt++。用id对应每个单词末尾结点的编号。
2.正常建立AC自动机。过程中记录出队顺序。
3.(我们一共有idx个结点),逆出队顺序遍历每个结点v[i],将cnt累加到回跳点上,就是ne[v[i]]上。
4.根据id找到对应单词末尾结点编号,输出该节点的cnt,就是该单词出现次数。
解释:
1.trie是一颗树,如果我们去掉所有树边,只留下匹配失败时回溯的边。
2.我们会发现,从回溯边都是树中深度较深的点指向深度较浅的点的,且是没有环和回路的。
3.也就是总体从叶子方向向根方向的一个有向无环图(DAG)。
4.建树是的出队顺序是树从根到叶子的拓扑序(只看树边)。
5.那么这个拓扑序的逆序,就是我们有向无环图的拓扑序(只看回跳边)。
6.trie插入时,所有结点cnt+1,是因为我们会遍历所有结点,
7.将结点v[i]的cnt累加到ne[v[i]]的cnt上。一个字符串中,每一段都可能成为其他出现单词。
8.由于ne数组会帮我们跳到最长前缀位置,
9.所以每次,如果真的包含该单词,那么一定最后会跳到单词末尾结点上。
10.因为该单词本身就是前后缀完全相同的最长匹配。
11.同时由于我们遍历了所有结点,所以不会有遗漏
如图所示,遍历每个点最终会沿着这个回跳边累加到对应的单词末尾点上。
插入4个单词:a,bc,abcd,d
对应出现次数:2,2,1,2
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 1e6 + 10;
const int R = (1 << 20) + 10;
const int Base = N / 2;
const int M = 1e6 + 10;
const int P = 1 << 10;
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
const double eps = 1e-4;
const int mod = 998244353;
int n, m, k;
int tr[N][26];
int cnt[N];
int ne[N];
int idx;
int id[201];
vector<int> v;
void insert(int ver, char *s)
{
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];
// 这个有点说法
//
cnt[p]++;
}
// 每个单词,结尾结点对应上出现的顺序
// 我们最终答案是累加到p这个结点上的
// 这样在最后输出答案的可以找到
id[ver] = p;
}
void build()
{
queue<int> q;
for (int i = 0; i < 26; i++)
{
if (tr[0][i])
{
q.push(tr[0][i]);
}
}
while (q.size())
{
int t = q.front();
q.pop();
v.push_back(t);
for (int i = 0; i < 26; i++)
{
int j = tr[t][i];
if (j)
{
ne[j] = tr[ne[t]][i];
q.push(j);
}
else
{
tr[t][i] = tr[ne[t]][i];
}
}
}
}
void solve()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
char s[N];
scanf("%s", s);
insert(i, s);
}
build();
for (int i = idx - 1; i >= 0; i--)
{
// 只看树边的拓扑序的逆序
// 就是只看回跳边的拓扑序
// 这里我们根据回跳边将单词出现次数累加到单词末尾结点上
// 由于ne数组会帮我们跳到最长前缀位置,
// 所以每次,如果真的包含该单词,那么一定最后会跳到单词末尾结点上
// 同时由于我们遍历了所有结点,所以不会有遗漏
cnt[ne[v[i]]] += cnt[v[i]];
}
for (int i = 1; i <= n; i++)
{
printf("%d\n", cnt[id[i]]);
}
}
int main()
{
int t = 1;
// scanf("%d", &t);
while (t--)
{
solve();
}
}