AcWing 142. 前缀统计（Trie）

2021-03-03 00:27

阅读：457

标签：查找 ret return ++ 字符 class abc its trie

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

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

输入格式

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

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

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

输出格式

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

每个答案占一行。

输入样例：

3 2

abc

efg

输出样例：

字典树裸题。注意要更改的一点就是把insert函数里的末尾标记改为以该点为末尾的字符串的个数（即end[p]++）。Search函数里设置一个cnt变量累加待查找字符串每个节点的以其为末尾的字符串的个数，如果p==0说明剩下的部分没有在字典树里出现过了，直接return cnt即可。

#include using namespace std;
int trie[1000005][26],tot=1;
int eend[1000005]={0};
void insert(string s)
{
    int len=s.size();
    int k,p=1;
    for(k=0;k)
    {
        int ch=s[k]-‘a‘;
        if(trie[p][ch]==0) trie[p][ch]=++tot;
        p=trie[p][ch];
    }
    eend[p]++;
}
int search(string s)
{
    int len=s.size(),k,p=1,cnt=0;
    cnt+=eend[p];
    for(k=0;k)
    {
        p=trie[p][s[k]-‘a‘];
        if(p==0) return cnt;
        cnt+=eend[p];
    }

    return cnt;
}
int main()
{
    int n,m;
    cin>>n>>m;
    int i;
    for(i=1;i)
    {
        string s;
        cin>>s;
        insert(s);
    } 
    for(i=1;i)
    {
        string s;
        cin>>s;
        coutendl;
    }
    return 0;
}

AcWing 142. 前缀统计（Trie）

标签：查找 ret return ++ 字符 class abc its trie

原文地址：https://www.cnblogs.com/lipoicyclic/p/13029123.html

上一篇：UVA - 10935：Throwing cards away I （简单模拟）

下一篇：Windows远程桌面出现身份证验证错误要求的函数不受支持

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

亲，登录后才可以留言！

AcWing 142. 前缀统计（Trie）

评论

热门文章

推荐文章

最新文章

置顶文章