C++中的后缀Trie

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应该使用字符串。

分析问题

如果你打印出来，你会看到你建立一个树扩展相应太信分支线索的。你这样做了，因为您一次插入一个字母，但这并不是一个线索的正常布局：

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

争取解决第一步：如果你想找到的线索结构的任何字母更正代码

，你需要更新你的搜索，探索不对应于当前节点的信分支，但对于被搜索的字母：

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。

但需要进一步努力纠正设计

设计应插入/搜索字符串s。这个想法是检查当前字符与s[0]和递归插入/搜索字符串的其余部分s.substr(1);

Answer 2

@Christophe - 感谢这么多的视频链接然而，示例代码的链接被打破，所以我从视频想出了这一点，有两个功能，即插入和搜索如下

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; 

} 

而且我得到以下输出：未找到

这是混乱，因为AB是在ST中发现戒指。

最后一点，我想了解这条线：

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

这是否意味着，我们正在为“A”的ASCII码，然后从当前字符的ASCII码减去？

谢谢