字典树详解

字典树是一种用于统计和排序大量的字符串的数据结构。它的原理是把具有相同前缀的字符建立一颗树。

例如，我们有字符acdr,aced,bde,asd,ceed,asdr,frt进行建树的话应该是这样：

字典树两个基本操作是：1.建树2.查询

1.建树

建树的方式两种一种是用数组建树，一种是链表建树。在acm和oi中常用的建树方式是数组建树，在这里我们主要讲解一下数组建树。二者建树的思想是一致的

假定给你n个字符，将每个字符插入树中其实就算完成了建树的过程。我们用二维数组tire来作为树的储存结构。
tire[rt][c] = index代表rt节点与index相连，且index节点代表以c字符为结尾的一个字符串。假定将str字符串插入字典树中，那么检测当前节点rt是否与str[i]相连，如果相连的话tire[rt][str[i]] > 0，如果不相连的话tire[rt][str[i]] == 0,这时候我们应该创建一个新的节点使得rt与str[i]相连。代码如下：

void insert(char* data)
{
	int len = strlen(data);
	rt = root;
	for(int i = 0; i < len; i++)  //建树的过程 
	{
		int y = data[i] - 'a';
		if(tire[rt][y] == 0)   //如果rt与data[i]不相连，就创建一个新的节点使两者相连 
		{
			tire[rt][y] = ++index;
		}
		rt = tire[rt][y];
	}
}

2.查询

查询过程因题目而异。
如Hdu_1251，这个题要在建树的过程中把每一个前缀的数量统计下来
代码如下:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long 
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 1e6;
int trie[N][30], num[N] = {0};
int root = 0, index = 1;
void insert(char* data)
{
    int len = strlen(data);
    int rt = root;
    for(int i = 0; i < len; i++)
    {
        int y = data[i] - 'a';
        if(trie[rt][y] == 0)
        {
            trie[rt][y] = index++;
        }
        rt = trie[rt][y];
        num[rt]++;
    }
}
int query(char* str)
{
    int len = strlen(str);
    int rt = root;
    for(int i = 0; i < len; i++)
    {
        int y = str[i] - 'a';
        rt = trie[rt][y];
        if(rt == 0)
        {
            return 0;
        }
    }
    return num[rt];
}

int main()
{
    char word[11];
     while(gets(word))
     {
       if(word[0]==NULL)    //空行。gets读入的回车符会自动转换为NULL。
             break;
         insert(word);
     }
     while(gets(word))
         printf("%d\n",query(word));
    return 0;
}