CH 1601 - 前缀统计 - [字典树模板题]

题目链接：传送门

描述
给定 $N$ 个字符串 $S_1,S_2,\cdots,S_N$，接下来进行 $M$ 次询问，每次询问给定一个字符串 $T$，求 $S_1 \sim S_N$ 中有多少个字符串是 $T$ 的前缀。输入字符串的总长度不超过 $10^6$，仅包含小写字母。

输入格式
第一行两个整数 $N,M$。接下来 $N$ 行每行一个字符串 $S_i$。接下来 $M$ 行每行一个字符串表示询问。

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

样例输入
3 2
ab
bc
abc
abc
efg

样例输出
2
0

模板（一个最最普通的字典树模板）：

namespace Trie

{

    const int SIZE=maxn*;

    int sz;

    struct TrieNode{

        int ed;

        int nxt[];

    }trie[SIZE];

    void init()

    {

        sz=;

        memset(trie,,sizeof(trie));

    }

    void insert(const string& s)

    {

        int p=;

        for(int i=;i<s.size();i++)

        {

            int ch=s[i]-'a';

            if(!trie[p].nxt[ch]) trie[p].nxt[ch]=++sz;

            p=trie[p].nxt[ch];

        }

        trie[p].ed++;

    }

    int search(const string& s)

    {

        int p=;

        for(int i=;i<s.size();i++)

        {

            p=trie[p].nxt[s[i]-'a'];

            if(!p) return ;

        }

        return trie[p].ed;

    }

};

题解：

字典树板子题，对上面的板子稍作修改即可。

AC代码：

#include<bits/stdc++.h>

using namespace std;

namespace Trie

{

    const int SIZE=1e6+;

    int sz;

    struct TrieNode{

        int ed;

        int nxt[];

    }trie[SIZE];

    void init()

    {

        sz=;

        memset(trie,,sizeof(trie));

    }

    void insert(const string& s)

    {

        int p=;

        for(int i=;i<s.size();i++)

        {

            int ch=s[i]-'a';

            if(!trie[p].nxt[ch]) trie[p].nxt[ch]=++sz;

            p=trie[p].nxt[ch];

        }

        trie[p].ed++;

    }

    int search(const string& s)

    {

        int res=;

        int p=;

        for(int i=;i<s.size();i++)

        {

            p=trie[p].nxt[s[i]-'a'];

            res+=trie[p].ed;

            if(!p) break;

        }

        return res;

    }

};

int n,m;

string s;

int main()

{

    cin>>n>>m;

    Trie::init();

    for(int i=;i<=n;i++)

    {

        cin>>s;

        Trie::insert(s);

    }

    for(int i=;i<=m;i++)

    {

        cin>>s;

        cout<<Trie::search(s)<<endl;

    }

}

巴特西

CH 1601 - 前缀统计 - [字典树模板题]

最新文章

热门文章