题目描述
blablabla
样例
blablabla
算法 略略略
贴个带上注解的代码。
代码是y大的。
注解是我写的。
可能会帮助到一些人理解 insert()函数的操作吧。(我是看了好久才看懂那步操作)
C++ 代码
#include <iostream>
using namespace std;
const int N = 500000, M = 1000010;
int n, m;
/*
son数组尽量开大一点吧,怕不够用。
可以把son数组看成一片连续的虚拟内存。
idx其实就是这个虚拟内存的指针 。
然后在插入字符串时,每新出现一个分支,
就要新开辟一片内存,对应下面代码的
if (!son[p][s]) son[p][s] = ++idx;(其实++idx改成++(++idx)也能过,因为idx只是用来指向新内存的,不过很浪费空间而已)
cnt[i]存储 在idx这个内存位置结束的字符串 有多少个。
*/
int son[N][26], cnt[N], idx;
char str[M];
void insert()
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int s = str[i] - 'a';
if (!son[p][s]) son[p][s] = ++idx;
p = son[p][s];
}
cnt[p] ++ ;
}
int search()
{
int p = 0, res = 0;
for (int i = 0; str[i]; i ++ )
{
int s = str[i] - 'a';
if (!son[p][s]) break;
p = son[p][s];
res += cnt[p];
}
return res;
}
int main()
{
scanf("%d%d", &n, &m);
while (n -- )
{
scanf("%s", str);
insert();
}
while (m -- )
{
scanf("%s", str);
printf("%d\n", search());
}
return 0;
}