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碼減去？

謝謝