1、什么是字典树
就是用来存放一定长度的字符串（长度不于过大），可以很快的查找一组字符串中某个字符串出现的次数
字典树是一种以空间换时间的算法,如果这个字典树存储的是a~z,那么一个字符下面对应26个字符,即长度为1的字符最多需要26个存储空间,长度为2的字符最多需要26*26个存储空间，长度为3的字符串最多需要26*26*26个存储空间。。。
c++实现：
#include <iostream> #include <cstdio> #include <cstring> #define MAX 26 using namespace std; /** * 字典树是一种以空间换时间的算法,如果这个字典树存储的是a~z,那么一个字符下面对应26个字符,即长度为1的字符最多需要26个存储空间,长度为2的字符最多需要26*26个存储空间 * 长度为3的字符串最多需要26*26*26个存储空间，。。。 */ typedef struct TreeNode { TreeNode *next[MAX], *p; int num; // str为当前所存储的字符串 char str[11]; }TreeNode; class DictTree { private: TreeNode *t, *max; TreeNode *create() { static int i; static TreeNode *nt; nt = new TreeNode(); nt->num = 0; for(i = 0;i < MAX;++i) { nt->next[i] = NULL; } return nt; } void deleteC(TreeNode *nt) { static int i; for(i = 0;i < MAX;++i) if(nt->next[i] != NULL) { deleteC(nt->next[i]); delete[] nt->next[i]; nt->next[i] = NULL; } } public: TreeNode *T; DictTree() { T = t = this->create(); t->p = NULL; max = t; } ~DictTree() { // 将字典树进行销毁 deleteC(T); } void insert(const char *str) { static int len, i; len = strlen(str); this->t = this->T; t = T; for(i = 0;i < len;++i) { if(t->next[str[i]-'a'] == NULL) { t->next[str[i]-'a'] = create(); t->next[str[i]-'a']->p = t; t = t->next[str[i]-'a']; strcpy(t->str, t->p->str); this->t->str[i] = str[i]; t->str[i+1] = '\0'; } else { t = t->next[str[i]-'a']; } } ++t->num; if(this->t->num > this->max->num) this->max = this->t; } // 将出现字符串最多的返回 TreeNode numMaxString() { return *this->max; } // 查询当前字符串出现的个数 long search(const char *str) { this->t = this->T; static int i, len; len = strlen(str); for(i = 0;i < len;++i) { if(t->next[str[i]-'a'] == NULL) { return 0; } t = t->next[str[i]-'a']; } return t->num; } }; int main() { DictTree dt; int T; char str[11]; scanf("%d", &T); while(T--) { scanf("%s", str); dt.insert(str); } TreeNode t = dt.numMaxString(); printf("%s %d\n", t.str, t.num); /* while(1) { scanf("%s", str); printf("%s %ld\n", str, dt.search(str)); }*/ return 0; }
可以ac 南阳acm题目290
http://acm.nyist.net/JudgeOnline/problem.php?pid=290
