题目描述

给定N个字符串S1,S2…SN，接下来进行M次询问，每次询问给定一个字符串T，求S1～SN中有多少个字符串是T的前缀。

输入字符串的总长度不超过106，仅包含小写字母。

输入格式
第一行输入两个整数N，M。

接下来N行每行输入一个字符串Si。

接下来M行每行一个字符串T用以询问。

输出格式
对于每个询问，输出一个整数表示答案。

每个答案占一行。

输入样例：
3 2
ab
bc
abc
abc
efg
输出样例：
2
0

算法1

(Trie树，字典树)

用Trie树计算就行了，每次遍历一遍看看这个字符有没有，如果有的话就让ans+=cnt[p],每次更新p

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

const int N = 1e6 + 10;

int n, m;
char str[N];
int son[N][26], idx, cnt[N];

void add(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];
    }
    cnt[p] ++;
}

int query(char str[])   
{
    int p = 0, ans = 0;
    for(int i = 0;str[i]; i ++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return ans;
        p = son[p][u];
        ans += cnt[p];
    }
    return ans;
}

int main()
{
    scanf("%d%d", &n,&m);

    for(int i = 0; i < n; i ++)
    {
        scanf("%s", str);
        add(str);
    }

    for(int i = 0; i < m ;i ++)
    {
        scanf("%s", str);
        cout << query(str) << endl;
    }

    return 0;
}