题目描述

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;
}