Trie(字典树，前缀树)_模板

时间：2022-10-31 22:56:38

Trie

Trie，又经常叫前缀树，字典树等等。

Trie，又称前缀树或字典树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，根节点不保存值，这样可以把几个开头不同的串连在一颗Trie上(如abc，efg)。Trie中的键通常是字符串(所以常叫字典树)。

优点
可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。

缺点
虽然不同单词共享前缀，但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针。

建树
两种建法：
(1) 多叉树：仅字母：26或52，各种字母，数字，符号组合：根据情况算吧，反正需要的空间贼大
(2) 兄弟儿子表示法：用链表，如链式前向星(个人比较喜欢)，遍历时间较上一种长

应用
(1)字符串检索
(2)用多叉树建的树可以实现字典序排序
(3)最长公共前缀
(4)AC自动机等会用到

促使我学习Trie的题目：UVA 11732 "strcmp()" Anyone?

并没有UVA链接，其他OJ大概也搜得到

这道题给出一个 strcmp() 函数的实现方式，我们要求的就是判断 ‘==’ 的次数

int strcmp(char *s, char *t)

{

    int i;

    for (i = ; s[i] == t[i]; i++)

        if (s[i] == ) return ;

    return s[i] - t[i];

}

题面

由于要比较最后的 0，那么字符串相等则答案加 2 * strlen(str) + 2，否则加 2 * ptr + 1，ptr为中断位置。

代码
我使用的是兄弟儿子表示法(很显然)，时间复杂度的话，不是很慢，还行吧 . . .

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #define CL(X,N) memset((X), (N), sizeof(X))

 using namespace std;

 typedef long long LL;

 const int maxl = 1e3 + , maxn = 4e3 + ;

 int n;

 char str[maxl];

 int son[maxn * maxl], bro[maxn * maxl], cnt[maxn * maxl];

 char trie[maxn * maxl];

 LL size = , ans = ;

 inline void Insert(char *s, int len) {

     int ptr, cur = ;

     for(int i = ; i <= len; ++i) {

         for(ptr = son[cur]; ptr; ptr = bro[ptr])

             if(trie[ptr] == s[i]) break;

         if(!ptr) {

             ptr = size++;

             trie[ptr] = s[i];

             bro[ptr] = son[cur];

             son[cur] = ptr;

             cnt[ptr] = ;

             son[ptr] = ;

         }

         ans += (cnt[cur] - cnt[ptr]) * ( * i + );

         if(i == len) {

             ans += cnt[ptr] * ( * i + );

             ++cnt[ptr];

         }

         ++cnt[cur];

         cur = ptr;

     }

     return ;

 }

 inline void Initialize(void) {

     son[] = bro[] = cnt[] = ;

     ans = ;

     size = ;

     return ;

 }

 int main(int argc, char **argv) {

 #ifdef LOCAL

     freopen("in.txt", "r", stdin);

 #endif

     int len, cas = ;

     while(~scanf("%d", &n) && n) {

         Initialize();

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

             scanf("%s", str);

             len = strlen(str);

             Insert(str, len);

         }

         printf("Case %d: %lld", ++cas, ans);

         putchar();

     }

     return ;

 }

相关文章