双数组trie树

网上翻了n多资料，结果都是源自于那篇 啊 阿拉伯的 论文。

谁能帮我解释哈。


现在我能明白的有：

1.base数组与check数组是一个长度相同的数组
2.base数组存储的daf的节点
3.check数组存储装填转换，具体就是check数组的值是 其上一个节点的base下标。


不明白的是cheeck和base是怎么构造出来了
网上就是那么一个s到t的转换公式

看好多次都没明白。

特别不明白的是 中间的空白区是怎么弄出来的

[ 本帖最后由 十一文 于 2010-10-28 09:01 编辑 ]

自己研究这代码看看吧 看懂了其实很简单的
#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;
}

可能 我说的 不是很清晰

你这个tire树是最基本的tire树，

我要看的双数组tire树