trie树 跟 树的存储-左儿子右兄弟 - uva 11732
trie树 和 树的存储--左儿子右兄弟 --- uva 11732
trie树也叫前缀树 , 是一种字符串的快速查找树 , 有就是一种树。
因为trie树 , 是一种树 ,因此我们先讨论树的存储。
树的存储:左儿子右兄弟
对于普通情况下的树 , 我们会采用儿子节点法 , 来存储 , 但在trie中 , 往往采用左儿子右兄弟的存储法 , 更为快速。
左儿子右兄弟就是说,在树中 , 每个结点有两个指针结点 , 一个指向其儿子 , 一个指向其兄弟。
一下的代码 , 我们是用数组来代替链表的 , 这样更方便。
代码:
#include <iostream> #include <stdio.h> using namespace std; #define maxn 100 struct node { char y; int next ; //儿子 int right; //兄弟 //void clear1() {next = -1 ; right = -1;} }trie[maxn]; int next = 1; char ch[maxn]; void init() { trie[0].next = trie[0].right = -1; } void insert() { int u = 0 , v; int i , j; bool flag; for(i = 0; ch[i] ; i++) { flag = false; for(v = trie[u].next ; v != -1; v = trie[v].right) { if(trie[v].y == ch[i]) { flag = true; break; } } if(!flag) { v = next++; trie[v].right = trie[u].next; trie[u].next = v; trie[v].next = -1; trie[v].y = ch[i]; } u = v; } } int main() { return 0; }
uva11732解法:
这个题目一看就知道是用trie树, 来存储每个单词 , 然后每加入一个单词 , 我们就计算需要计算多少次 , 这样就能得到总的次数。然后当我们用普通的树存储方法时 , 就肯定会超时 , 因此需要使用 左儿子右兄弟的存储法。
比较是:
1、两个相同字符 2次
2、两个不同字符 1次
3、'/0' 和 '/0' 2次
4、'/0' 和其他字符 1次
代码:
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; #define maxn 4000010 struct node { char y; int son; //指向儿子 int right; //指向右边的兄弟节点 int sum ; //表示有多少个儿子 }trie[maxn]; int ch[123]; char str[1010]; int n , trie_s ; long long sum ; void init() { trie[0].son = trie[0].right = -1; trie[0].sum = 0; sum = 0; trie_s = 1; } void insert1() { int i , j , k = strlen(str); //int x , y = 0; int u = 0; bool flag; for(i = 0; i <= k ; i++) { flag = false; for(j = trie[u].son ; j != -1 ; j = trie[j].right) { if(trie[j].y == str[i]) { flag = true; break; } } if(!flag) { j = trie_s++; trie[j].right = trie[u].son; trie[j].y = str[i]; trie[u].son = j; //trie[u].sum += 1; //记录有多少儿子 trie[j].sum = 0; trie[j].son = -1; } if(i == k) { sum += trie[u].sum+trie[j].sum; trie[j].sum++;} //特判结尾 Trie中不会进入结尾字符,需特判统计 else sum += (trie[u].sum+trie[j].sum); trie[u].sum++; u = j; //trie[u].sum += 1; //记录有多少儿子 //sum += trie[u].sum+trie[j].sum-1; //u = j; } //sum += trie[u].sum+trie[u].p*2; //trie[u].p += 1; } int main() { int cas = 1; int i ; while(scanf("%d" , &n) && n) { init(); for(i = 1; i <= n; i++) { scanf("%s" , str); insert1(); } cout<<"Case "<<cas++<<": "; cout<<sum<<endl; //printf("%I64d\n" , sum); } return 0; } /* 2 a b 4 cat hat mat sir 0 */