|
|
#2
sock2582010-10-27 17:35
自己研究这代码看看吧 看懂了其实很简单的
#include<iostream> using namespace std; const int kind=26;//字母种类 struct Treenode//树的结点结构 { int count;//这个附加变量在本题中记录遍历到该结点形成的字符串出现的次数,在不同题中可记录不同的内容。 Treenode *next[kind];//指向儿子结点,有26个结点; Treenode()//每个结点的初始化 { count=1; for(int i=0;i<kind;i++) next[i]=NULL; } }; void insert(Treenode *&root,char *word)//向以root为根结点的树中插入串word { Treenode *location=root; int i=0,branch=0; if(location==NULL) {location=new Treenode();root=location;} while(word[i]) { branch=word[i]-'a'; if(location->next[branch]) location->next[branch]->count++;//如果该字符存在,串数量加1 else location->next[branch]=new Treenode();//如果不存在,建新结点 i++; location=location->next[branch];//链表结点下移 } } int search(Treenode *root,char *word)//查找,与插入类似 { Treenode *location=root; int i=0,branch=0,ans; if(location==NULL) return 0; while(word[i]) { branch=word[i]-'a'; if(!location->next[branch]) return 0; i++; location=location->next[branch]; ans=location->count; } return ans; } int main() { char word[10]; char ask[10]; Treenode *root=NULL; while(gets(word)) { if(word[0]=='\0') break; insert(root,word); } while(gets(ask)) cout<<search(root,ask)<<endl; return 0; } |
双数组trie树
网上翻了n多资料,结果都是源自于那篇 啊 阿拉伯的 论文。
谁能帮我解释哈。
现在我能明白的有:
1.base数组与check数组是一个长度相同的数组
2.base数组存储的daf的节点
3.check数组存储装填转换,具体就是check数组的值是 其上一个节点的base下标。
不明白的是cheeck和base是怎么构造出来了
网上就是那么一个s到t的转换公式
看好多次都没明白。
特别不明白的是 中间的空白区是怎么弄出来的
[ 本帖最后由 十一文 于 2010-10-28 09:01 编辑 ]