前缀统计

落日映苍穹つ 2021-11-01 11:22 309阅读 0赞

题目链接：[https://www.acwing.com/problem/content/144/][https_www.acwing.com_problem_content_144]

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

思路：可以把这N个字符串插入一棵Trie字典树,Trie树的每个节点上存储一个整数ans，记录该节点是多少个字符串的末尾节点。对于每个询问，在Trie

树中检索T，在检索过程中累加途径的每个节点的cnt值，就是该询问的答案

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int trie[1000010][30],b[1000010];
    int tot=1;
    char a[1000010];
    void insert(char a[])
    {
        int n=strlen(a);
        int p=1;
        for(int i=0;i<n;i++)
        {
            int w=a[i]-'a';
            if(trie[p][w]==0)
                trie[p][w]=++tot;
            p=trie[p][w];
        }
        b[p]++;
        return;
    }
    int fun(char a[])
    {
        int n=strlen(a);
        int sum=0,p=1;
        for(int i=0;i<n;i++)
        {
            int w=a[i]-'a';
            if(trie[p][w]==0)
                break;
            p=trie[p][w];
            sum+=b[p];
        }
        return sum;
    }
    int main()
    {
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=0; i<n; i++)
        {
            scanf("%s",a);
            insert(a);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%s",a);
            int sum=fun(a);
            printf("%d\n",sum);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/zcb123456789/p/11299875.html

[https_www.acwing.com_problem_content_144]: https://www.acwing.com/problem/content/144/

发表评论取消回复

表情：

评论列表（有 0 条评论，309人围观）

还没有评论，来说两句吧...

相关阅读

相关 1248. 统计「优美子数组」前缀和的运用

再次分享一道前缀和的题目可以说，它在 [560. 和为 K 的子数组前缀和的运用][560. _ K _] 上面套了壳本质都是计算前缀和数组，然后用 Map 优化访

骑猪看日落/ 2023年02月08日 12:48/ 0 赞/ 111 阅读

相关 HDU 1251-统计难题（字典树-统计前缀串）

统计难题 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others

ゝ一世哀愁。/ 2022年08月21日 13:47/ 0 赞/ 169 阅读

相关 CUDA函数前缀与存储器前缀讨论

在CUDA C语言对C语言的扩展之一就是加入了一些函数前缀和存储器前缀，它们是：函数前缀： \_\_device\_\_ , \_\_global\_\_, \_\_ho

偏执的太偏执、/ 2022年08月08日 04:29/ 0 赞/ 132 阅读

相关前缀判断

如下的代码判断needle\_start指向的串是否为haystack\_start指向的串的前缀，如不是，则返回NULL。比如："abcd1234"

逃离我推掉我的手/ 2022年08月04日 16:42/ 0 赞/ 144 阅读

相关英语前缀总结

常见的前缀 1. 表示否定意义的前缀 1）纯否定前缀 a- ，an- ， asymmetry (不对称) anhydrous (无水的) Dis- disho

痛定思痛。/ 2022年06月11日 02:11/ 0 赞/ 2753 阅读

相关 python3 三种字符串（无前缀，前缀u，前缀b）与encode()

假设读者已经了解了什么叫字符集，什么叫编码，什么叫解码。首先要明确，虽然有三种前缀（无前缀，前缀u，前缀b），但是字符串的类型只有两种（str，bytes），实验如下：

缺乏、安全感/ 2022年05月23日 00:46/ 0 赞/ 260 阅读

相关前缀树

是一种哈希树的变种。典型应用是用于统计，排序和保存大量的[字符][Link 1]串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀

ゞ浴缸里的玫瑰/ 2022年05月10日 12:26/ 0 赞/ 195 阅读

相关前缀树

最近看代码，发现了一个敏感词检测是用前缀树写的，看起来速度蛮快，毕竟是拿空间换时间，LOG倍速。但是缺点也很明显，待检测文本需要与敏感词词库中的值完全匹配。所以对于简短的词法比

淡淡的烟草味﹌/ 2022年04月04日 06:48/ 0 赞/ 305 阅读

相关前缀统计

题目链接：[https://www.acwing.com/problem/content/144/][https_www.acwing.com_problem_content_

落日映苍穹つ/ 2021年11月01日 11:22/ 0 赞/ 310 阅读

相关段前缀

. 什么是段前缀出现在访问内存单元的指令中，用于显式

系统管理员/ 2021年05月03日 16:22/ 0 赞/ 496 阅读