在 C++ 中构建前缀 Trie，后缀 Trie

Question

我已经使用 video 来理解前缀 trie（尽管最终我试图最终得到后缀 trie）但是示例代码的 link 被破坏了所以我来了从视频开始，有两个功能，即插入和搜索，如下所示

  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;
}

然后主要实现如下：

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 码中减去？

谢谢

Answer 1

后缀树和前缀树之间存在一些差异。

前缀树 - 它是一棵树，其中包含 所有单词（或由某个符号分隔的其他一些块）来自给定文本 .例如。对于文本 "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's algorithm，它在线性时间内工作。

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

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

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

在 C++ 中构建前缀 Trie，后缀 Trie

Building a Prefix Trie in C++, Suffix Trie

c++

trie

suffix