Suffix Trie in C++

Question

Bir kod ekinde bir C++ kodu yazmaya çalışıyorum, ancak bu kodun, bir soneki ya da alt dizinin son eklenme sırasında görünen sıklıklarının her bir düğümdeki sayaçlarını takip etmesini istiyorum: sadece 4 karakterden A, C, G ve T

aşağıdaki kod benim girişimi ancak olduğu ile çalışıyorum o düzgün çalışmıyor onun:

#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

sorun onun tasarım arama ve hakkında yanlış olmasıdır insert: tek karakter için yaparsınız, trie ise bir string ile çalışmalıdır. Eğer siz de mektubu gelen şube genişleyen bir ağaç oluşturmak olduğunu göreceksiniz tray çıktısını Eğer sorun

ait

analizi. Bir kerede bir harf eklemek için bu yapmış ancak bu bir tray normal düzen değil: Bir element için arama yaparken kök öğeyi ise

Benzer

,, her şeydir tamam. Ancak, kök öğesi değilse, kodunuz her zaman geçerli düğüme karşılık gelen dalı arar ve bu yinelemeli olarak, yalnızca köke karşılık gelen dalda arama yapacağı anlamına gelir.

çözüm yolunda

İlk adımı : Eğer tray yapısındaki herhangi bir harf bulmak istiyorsanız kodunu

düzeltin keşfetmek için aramanızı güncellemeniz gerekmez geçerli düğümün harfine karşılık gelen şube Ancak, aranan harf:

Bu, alttaki tasarımı değil, kodu düzeltir. Burada bir online demo here.

Ama daha fazla çalışma tasarım tasarım/insert bir dize s aramalıyız

düzeltmek için gereklidir. Fikir şu anki char'i s[0] ile kontrol etmek ve s.substr(1) dizgesinin kalanını art arda eklemek/aramak;

Answer 2

@Christophe - Ben videodan bu geldi ancak örnek kod link yüzden bozuldu video bağlantısı için çok teşekkürler, iki işlev eklemek ve arama orada yani olduğu gibi aşağıda

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; 

} 

Ve şu çıktıyı alıyorum: ab st bulunur beri

Bu kafa karıştırıcı bulunamadı şöyle Sonra ana uygulamaya yüzük s.

Ve son olarak bu çizgiyi anlamaya çalışıyorum:

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

demek biz 'a' için ASCII kodu alma ve daha sonra akım karakterinin ASCII kodundan çıkarma edilir ki?

Teşekkür ederiz