AcWing 1282. 搜索关键词
原题链接
中等
作者:
只想白嫖
,
2022-01-09 22:42:36
,
所有人可见
,
阅读 179
//author: A Fei
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e4 + 10, M = 1e6 + 10;
int tr[N * 53][26];
int q[N * 53], idx, ne[N * 53], cnt[N * 53];
char s[M];
int n, T;
void insert()
{
int j = 0;
for(int i = 0; s[i]; i ++)
{
int t = s[i] - 'a';
if(!tr[j][t]) tr[j][t] = ++idx;
j = tr[j][t];
}
cnt[j] ++;
}
void get_next()
{
int hh = 0, tt = -1;
for(int i = 0; i < 26; i ++)//0号点应指向自己即0号点的ne为0,所以直接将0号节点的儿子放进队列中
if(tr[0][i]) q[++ tt] = tr[0][i];
while(hh <= tt)
{
int t = q[hh++]; //从队列中拿出来的idx为前i-1层的idx;类比到kmp:t --> i-1
for(int i = 0; i < 26; i ++)//遍历t节点的儿子
{
int p = tr[t][i]; //t节点的i号儿子就是当前找ne事的第i层点;类比到kmp:p --> i;
/*
优化:
当匹配失败向前跳转,先将其直接一步跳到位,跳到该跳的地方
(类似于数据结构里面nextval[]去优化kmp)
为啥下面的直接指向父节点指向的地方即可,可以这样想一下(数学归纳):
前父节点已经一步到位了,那么该点直接指向父节点指向的地方也即指向一步到位的地方了
*/
if(!p) tr[t][i] = tr[ne[t]][i];//如果p点不存在:就将该节点指向父节点ne指向的地方tr[ne[t][i]
else//p存在就计算p的ne:指向父节点ne指向节点的i号儿子tr[ne[t][i];
{
ne[p] = tr[ne[t]][i];
q[++ tt] = p;//将节点p放进队列中
}
}
}
}
int main()
{
scanf("%d", &T);
while(T --)
{
idx = 0;
memset(tr, 0, sizeof tr);
memset(ne, 0, sizeof ne);
memset(cnt, 0, sizeof cnt);
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
scanf("%s", s);
insert();//建立单词的 tire 树
}
get_next();//得到next数组
scanf("%s", s);
LL res = 0;
for(int i = 0, j = 0; s[i]; i ++)
{
int t = s[i] - 'a';
j = tr[j][t];//将儿子的idx赋值给j,每次循环j都向下走
int p = j;
while(p)//每到一个节点,就找他ne[],能走到的单词并将其数量加和
{
res += cnt[p];
cnt[p] = 0;//加完之后初始化为0
p = ne[p];//继续往下找ne能到的地方,若不是单词的话cnt就为0
}
}
printf("%lld\n", res);
}
return 0;
}