AcWing 142. 前缀统计
原题链接
简单
作者:
笨蛋小狗要加油
,
2023-10-06 19:50:53
,
所有人可见
,
阅读 53
Tire树模板题变形
这是 cf麦麦
的第一篇题解~
样例
3 2
ab
bc
abc
abc
efg
输出
2
0
思路
先通过idx进行路线标记(树节点哪些被用过),在遍历 for (str[i])后,打上标记(最后一个字符);
统计时,先特判是否存在儿子,没有直接return 0; 有的话一直往下递。一路上,如果cnt[p]有值就加上
这里要注意不能让 p = son[p][u]; cnt[p]++;因为p是从1开始的,写反会导致最后一个cnt[p]加不到
代码奉上
#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
void insert(char str[])
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u]; // 第一个的idx就是1
}
cnt[p] ++;
}
int query(char str[])
{
int p = 0,has = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return has; // 为空直接输出结果
// p 是从开始的,所以如果交换这两个顺序,会导致最后一个p加不到!
p = son[p][u];
has += cnt[p];
}
return has;
}
int main()
{
int n, m;
cin >> n >> m;
while (n -- ) {
scanf("%s", str);
insert(str);
}
while (m -- ) {
scanf("%s", str);
printf("%d\n",query(str));
}
}