1

我已经使用视频来理解前缀 trie（尽管最终我试图到达后缀 trie）但是示例代码的链接已损坏，所以我从视频中想出了这个，有两个函数，即插入并搜索如下

  void insert(string word)
{
    node* current=head;
    current->prefix_count++;
    for(unsigned int i=0;i<word.length();++i)
    {
        int letter=(int)word[i]-(int)'a';
        if (current->child[letter]==NULL)
            current->child[letter]=new node();
        current->child[letter]->prefix_count++;
        current=current->child[letter];
            }
    current->is_end=true;
}

bool search(string word)
{
    node *current=head;
    for(int i=0;i<word.length();++i)
    {
        if(current->child[((int)word[i]-(int)'a')]==NULL)
            return false;
        current=current->child[((int)word[i]-(int)'a')];
    }
    return current->is_end;
}

然后实现main如下：

int main(){
node* head=NULL;

 string s="abbaa";
 init();
 insert(s);
 if(search("ab")==true) cout<<"Found"<<endl;
 else cout<<"Not found"<<endl;

}

我得到以下输出：未找到

这很令人困惑，因为在字符串 s 中找到了 ab。

最后我试图理解这一行：

int letter=(int)word[i]-(int)'a';

这是否意味着我们正在获取 'a' 的 ASCII 码，然后从当前字符的 ASCII 码中减去？

谢谢

4

1 回答 1

0

后缀树和前缀树之间有一些区别。

前缀树 - 它是一棵树，它包含来自给定文本的所有单词（或由某个符号分隔的其他一些块）。例如对于文本“you have a text”，前缀树包含 4 个单词：[“you”、“have”、“a”、“text”]（但不包括“hav”）。

后缀树 - 它是一个前缀树，它包含来自给定单词的所有后缀 。例如对于字符串“abacaba”，后缀树包含 7 个单词：[“abacaba”、“bacaba”、“acaba”、“caba”、“aba”、“ab”、“a”]。

后缀树的幼稚实现基于前缀树实现，该实现由 O(N^2) 中某个输入字符串的所有子字符串填充（因此，在您的代码中，您应该将字符串 S 的所有后缀插入到 Trie 中），但是您可以找到更聪明的 Ukkonen 算法，它在线性时间内工作。

通常，当您想在文本中查找单词（例如从某些字典等）时使用前缀树；后缀树用于查找某些模式作为文本的子字符串。

所以，你应该根据你的问题选择你需要的树。

是的，你的最后一个问题是对的。

于 2016-04-11T11:48:12.793 回答