acwing 142. 前缀统计

2021-01-30 10:15

阅读：533

标签：题解 har iostream break res msu std 答案字符

题面：

给定N个字符串 $S_{1}, S_{2} \dots S_{N}$

输入字符串的总长度不超过 $10^{6}$

输入格式

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

接下来N行每行输入一个字符串 $S_{i}$

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

输出格式

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

每个答案占一行。

输入样例：

3 2
ab
bc
abc
abc
efg

输出样例：

2
0
题解：
这是比较裸的trie题

#include
#include
#include
#includeusing namespace std;
int son[1000010][26],cnt[1000010],idx;
char str[1000010];
void insert()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int &s=son[p][str[i]-‘a‘];
        if(!s)s=++idx;
        p=s;
    }
    cnt[p]++;
}
int query()
{
    int p=0;int res=0;
    for(int i=0;str[i];i++)
    {
        int &s=son[p][str[i]-‘a‘];
        if(!s)break;
        p=s;
        res+=cnt[p];
    }
    return res;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while(n--)
    {
        scanf("%s",str);
        insert();
    }
    while(m--)
    {
        scanf("%s",str);
        printf("%d\n",query());
    }
    return 0;
}

acwing 142. 前缀统计

标签：题解 har iostream break res msu std 答案字符

原文地址：https://www.cnblogs.com/flyljz/p/11659965.html

上一篇：workman初次接触,可以正常运行在Windows站点下.

下一篇：ShowDoc上手构建api文档

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：acwing 142. 前缀统计
文章链接：http://soscw.com/index.php/essay/49084.html

亲，登录后才可以留言！

acwing 142. 前缀统计

输入格式

输出格式

输入样例：

输出样例：

评论

热门文章

推荐文章

最新文章

置顶文章