trie数和后缀树

1.trie树

字典树（trie）可以保存一些字符串->值的对应关系，字典树的插入和查询时间复杂度都是O（k），其中k是key的长度，与字典树中保存元素数无关。其缺点是空间消耗高。

其核心思想是以空间换时间。利用字符串的公共前缀来降低查询时间开销已达到提高效率的目的。

trie树的结点信息结构体：

struct TrieNode{int count;     //统计该结点的单词出现的次数bool exist;    //标记该结点是否构成单词TrieNode *next[26];  //指针数组，数组的元素的类型是TrieNode*
};

trie树的插入和查找：

#include <iostream>
using namespace std;struct TrieNode{int count;     //统计该结点的单词出现的次数bool exist;    //标记该结点是否构成单词TrieNode *next[26];  //指针数组，数组的元素的类型是TrieNode*
};/*创建一个结点*/
TrieNode *CreateTrieNode()
{TrieNode *node = new TrieNode();node->count = 0;node->exist = 0;  //该结点不构成单词memset(node->next, 0, sizeof(node->next));  //将next指向的连续区域初始化为空return node;
}/*往trie树里插入单词*/
void TrieInsert(TrieNode *root, char *word)
{if (word == NULL) return;TrieNode *node = root;char *str = word;int id;while (*str){id = *str - 'a';if (node->next[id] == NULL){node->next[id] = CreateTrieNode();}node = node->next[id];//node->count++;     //如果要统计以某个字符串为前缀的数量，在次数加++str;}node->exist = true;   //构成单词node->count++;        //如果要统计某个单词出现的次数，在次数加
}/*查找某一个单词出现次数*/
int TrieSearch(TrieNode *root, char *word)
{if (word == NULL) return 0;TrieNode *node = root;char *str = word;int id;while (*str){id = *str - 'a';node = node->next[id];if (node == NULL) return 0;++str;}return node->count;
}int main(void)
{TrieNode *root = CreateTrieNode();     // 初始化字典树的根节点  char str[12];bool flag = false;while (gets_s(str,12)){if (flag)printf("%d\n", TrieSearch(root, str));else{if (strlen(str) != 0){TrieInsert(root, str);}elseflag = true;}}return 0;
}

参考：http://blog.csdn.net/hackbuteer1/article/details/7964147

2.后缀树
后缀树就是一颗压缩后的Trie，存储了字符串的所有后缀。