hiho1014 Trie树

本来想顺便写个trie的教程，无奈手头没有专业的画图工具，还是等暑假再补上吧。

链

hiho

解

要求相同前缀个数的话，只需要在每一个节点维护一个变量用来记录子串数量。维护很简单，只需要每增加一个字符串时从根走下对每一个经过的节点的该变量加一即可。【啊啊啊我废话好多
多说一句现在数据结构在下真是写得越来越专业了……对比一下以前模仿lrj写的简直就是【】

码

#include <iostream>
using namespace std;
template<int maxn, int sigma = 26>
class Trie
{
private:
    struct Node
    {
        Node *ch[sigma];
        int cnt;
    }*root, pool[maxn * 2];
    int cnt;
    inline int idx(char c){return c - 'a';}
public:
    Trie()
    {
        root = &pool[0];
        cnt = 1;
    }
    void add(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                p -> ch[idx(s[i])] = &pool[cnt++];
            p -> ch[idx(s[i])] -> cnt++;
            p = p -> ch[idx(s[i])];
        }
    }
    int go(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                return 0;
            p = p -> ch[idx(s[i])];
        }
        return p -> cnt;
    }
};
Trie<1000000> trie;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        trie.add(s);
    }
    int m;
    cin>>m;
    while(m--)
    {
        string s;
        cin>>s;
        cout<<trie.go(s)<<endl;
    }
    return 0;
}

再附一个节点池的炫酷指针版

#include <iostream>
using namespace std;
template<int maxn, int sigma = 26>
class Trie
{
private:
    struct Node
    {
        Node *ch[sigma];
        int cnt;
    }*root, *nodecur, pool[maxn * 2];
    inline int idx(char c){return c - 'a';}
public:
    Trie()
    {
        root = &pool[0];
        nodecur = &pool[1];
    }
    void add(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                p -> ch[idx(s[i])] = nodecur++;
            p -> ch[idx(s[i])] -> cnt++;
            p = p -> ch[idx(s[i])];
        }
    }
    int go(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                return 0;
            p = p -> ch[idx(s[i])];
        }
        return p -> cnt;
    }
};
Trie<1000000> trie;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        trie.add(s);
    }
    int m;
    cin>>m;
    while(m--)
    {
        string s;
        cin>>s;
        cout<<trie.go(s)<<endl;
    }
    return 0;
}

话说指针这东西千万不要乱用啊【捂脸熊】，用得不好会出人命的啊……