本文共 1547 字，大约阅读时间需要 5 分钟。
今天AC了两题trie tree的题目,感觉trie的性质真的是相当的好，而且实现比较简单。它使在字符串集合中查找某个字符串的操作的复杂度降到最大只需O(n),其中n为字符串的长度。trie是典型的将时间置换为空间的算法，好在ACM中一般对空间的要求很宽松。 #include #include using namespace std;class trie{public: trie* next[26]; int num; //记录前缀的个数 bool value; //标记这里是不是一个单词 trie() { for(int i=0;i<26;i++) next[i]=0; value=0; num=0; }}root;void insert(char* s){ trie *p=&root; int k=0; while(s[k]!='\0') { if(!p->next[s[k]-'a']) p->next[s[k]-'a']=new trie; p=p->next[s[k]-'a']; p->num++; 每访问节点就++1次，多好啊！ k++; } p->value=1; //在这里可根据具体题意来加东西}int find(char *s){ trie* p=&root; int k=0; while(s[k]!='\0'&&p->next[s[k]-'a']) { p=p->next[s[k]-'a']; k++; } if(s[k]=='\0') return p->num; return 0;}int main(){ char english[12],martian[12],word[12]; while(gets(english)&&english[0]!='\0') { insert(english); } while(scanf("%s",martian)!=EOF) { cout< <
说明：这题是1组的数据的，如果是多组数据，要在主函数里加上：
---------------------------------------------
trie *p=&root;char ask1[20000];while(){For(){insert(p,ask1); find(p,ask1); } P=new trie();//注意这里 多组数据要建多个树} ---------------------------------------同时还要修改insert(trie *p,char *s) Find(trie *p,char *s) ----------------------------------------
自己做题体会吧！
练习题目：所有字符串的题目，可以考虑用trie！
HDU:1251，1075，1800，2072都是。
陈宇老师写的，非常好！
转载地址：http://jcali.baihongyu.com/