接尾辞トライC++

Question

私はサフィックストライのC++コードを書こうとしていますが、このコードでは、接尾辞トライの構築中に文字や部分文字列がどのくらいの頻度で出現するかを各ノードのカウンタに記録しておきます。唯一の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

問題は、その設計が検索に欠陥があるということで、挿入：あなたは1文字のためにそれを行いますが、trieは文字列で動作するはずです。あなたはあなたがあまりにも手紙を対応するブランチを展開し、ツリーを構築していることがわかりますトライをプリントアウトした場合、問題

の

分析。

同様

、あなたは要素を検索したときには、ルート要素の場合、すべてがある、：あなたは一度に一つの文字を挿入するが、これはトライの通常のレイアウトではありませんので、あなたはこれを行ってきましたOK。しかし、それがルート要素でない場合、コードは常に現在のノードに対応するブランチとこれを再帰的に検索します。つまり、ルートに対応するブランチでのみ検索します。

は解決に向けた

まずステップを ：あなたがトライ構造の任意の文字を検索したい場合は、コード

を修正し、あなたが探検に検索を更新する必要はありません、現在のノードの文字に対応するブランチ検索された文字に置き換えられます。

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に発見されたので、これは混乱して

が見つかりませんを次のようにメインを実装リングs。

そして最後に、私はこの行を理解しようとしています：

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

これは我々が「A」のASCIIコードを取得して、現在の文字のASCIIコードから減算されている意味ですか？

ありがとうございました