C++ 中的后缀树

Question

我一直在尝试编写后缀 trie 的 C++ 代码，但是我希望此代码跟踪每个节点的计数器，以了解在后缀 trie 构造期间字符或子字符串出现的频率：记住我仅使用 4 个字符 A、C、G 和 T

下面的代码是我的尝试，但它不能正常工作：

#include<iostream>
#include <string>
#include <stdio.h>
#include <string.h>
using namespace std;

struct SuffixTreeNode{
    char c;
    struct SuffixTreeNode* one;
    struct SuffixTreeNode* two;
    struct SuffixTreeNode* three;
    struct SuffixTreeNode* four;
    //int count;

};

SuffixTreeNode* CreateNode(char ch){
    SuffixTreeNode* newnode=new SuffixTreeNode();
    newnode->c=ch;
    newnode->one=NULL;
    newnode->two=NULL;
    newnode->three=NULL;
    newnode->four=NULL;
    //count=0;
}   

SuffixTreeNode* Insert(SuffixTreeNode* root,char ch){
    if (root==NULL){
        root=CreateNode(ch);
    }
    else if(ch=='a'){
        root->one=Insert(root->one,ch);
    }
    else if(ch=='c'){
        root->two=Insert(root->two,ch);
    }
    else if(ch=='g'){
        root->three=Insert(root->three,ch);
    }
    else if(ch=='t') {
        root->four=Insert(root->four,ch);
    }

    return root;
}

bool Search(SuffixTreeNode* root, int data){
    if(root==NULL) return false;
    else if (root->c==data) return true;
    else if (root->c=='a')return Search(root->one,data);
    else if (root->c=='c')return Search(root->two,data);
    else if (root->c=='g')return Search(root->three,data);
    else return Search(root->four,data);
}

int main(){
    SuffixTreeNode* root=NULL;
    char str;
    root=Insert(root,'a');
    root=Insert(root,'c');
    root=Insert(root,'c');
    root=Insert(root,'t');
    root=Insert(root,'a');
    root=Insert(root,'g');
    cout<<"Enter character to be searched\n";
    cin>>str;

    if(Search(root,str)==true)cout<<"Found\n";
    else cout<<"Not found\n";
}

Answer 1

问题是它的设计对于搜索和插入是有缺陷的：你这样做是为了单个字符，而 trie 应该适用于字符串。

问题分析

如果你打印出 trie，你会看到你构建了一棵树，扩展了与字母对应的分支。你这样做是因为你一次插入一个字母，但这不是 trie 的正常布局：

同样，当你搜索一个元素时，如果它是根元素，一切都可以。但如果它不是根元素，你的代码将始终搜索与当前节点对应的分支，并且这是递归的，这意味着它只会在与根对应的分支中搜索。

迈向solution:correct代码的第一步

如果要在 trie 结构中查找任何字母，则需要更新搜索以探索与当前节点的字母对应的分支，而是搜索到的字母：

bool Search(SuffixTreeNode* root, int data){
    cout << (char)data<<"=="<<root->c<<"?"<<endl; 
    if(!root) return false;
    else if (root->c==data) return true;
    else if (data=='a')return Search(root->one,data);
    else if (data=='c')return Search(root->two,data);
    else if (data=='g')return Search(root->three,data);
    else return Search(root->four,data);
}

这更正了代码，而不是底层设计。这里有一个online demo here。

但需要进一步的工作来纠正设计

设计应该insert/search一个字符串s。这个想法是用 s[0] 检查当前字符并递归地 insert/search 剩余的字符串 s.substr(1);

Answer 2

@Christophe - 非常感谢视频 link 但是示例代码的 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 码中减去？

谢谢

C++ 中的后缀树

Suffix Trie in C++

c++

suffix-tree