【C/C++】字典树

引用书籍：《算法竞赛入门到进阶》清华大学出版社

字符串匹配问题

• 有这样一个字符串的问题：在n个字符串中查找某个字符串是否存在？
• 如果使用暴力的做法，逐个来匹配每个字符串，复杂度是O(nm)，m是字符串的平均长度，这种做法效率很低。
• 字典树：在上述问题中，如果像查字典一样，比如要查找单词"dog"，先翻到字典中d对应的部分，再按顺序查找'o'和'g'。效率要高很多，字典树就是模拟这种操作的数据结构。

例题(hdu 1251)

• 用map实现：

#include<bits/stdc++.h>

using namespace std;

int main(){
    char str[12];
    map<string, int>m;
    while(fgets(str, 12, stdin)){ //也可以使用gets函数读入字符串，循环体的内容需要做微小的改动
        int len = strlen(str);
        if(len==1) break;
        for(int i=len-1; i>0; i--){
            str[i] = '\0';
            m[str]++;
        }
    }
    while(~scanf("%s",str)) printf("%d\n",m[str]);
    return 0;
}

• 用字典树实现(数组)

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e4 + 10;
int tire[maxn*10][26];
int book[maxn*10];
int cnt;

void Insert(char *str){
    int len = strlen(str);
    int root = 0;
    for(int i=0; i<len; i++){
        int id = str[i] - 'a';
        if(!tire[root][id]) tire[root][id] = ++cnt;
        root = tire[root][id];
        book[root]++;
    }
}

int Find(char *str){
    int len = strlen(str);
    int root = 0;
    for(int i=0; i<len; i++){
        int id = str[i] - 'a';
        if(!tire[root][id]) return 0;
        root = tire[root][id];
    }
    return book[root];
}

int main(){
    cnt = 0;
    memset(tire, 0, sizeof(tire));
    memset(book, 0, sizeof(book));
    char str[12];
    while(gets(str)){
        if(!strlen(str)) break;
        Insert(str);
    }
    while(gets(str)) printf("%d\n",Find(str));
    return 0;
}

• 字典树还可以使用结构体指针来实现，但是空间复杂度相比于数组要差一些，因此并不常用，在此题中也会MLE

#include<bits/stdc++.h>

using namespace std;

struct Trie{
    Trie * next[26];
    int num;
    Trie(){
        for(int i=0; i<26; i++) next[i] = NULL;
        num = 0;
    }
};
Trie root;

void Insert(char *str){
    int len = strlen(str);
    Trie *p = &root;
    for(int i=0; i<len; i++){
        int id = str[i] - 'a';
        if(p->next[id] == NULL)
            p->next[id] = new Trie;
        p = p->next[id];
        p->num++;
    }
}

int Find(char *str){
    Trie *p = &root;
    for(int i=0; str[i]; i++){
        int id = str[i] - 'a';
        if(p->next[id] == NULL)
            return 0;
        p = p->next[id];
    }
    return p->num;
}


int main(){
    char str[12];
    while(gets(str)){
        if(!strlen(str)) break;
        Insert(str);
    }
    while(gets(str)) printf("%d\n",Find(str));
    return 0;
}