Suffix Trie in C++

Question

Я пытался написать код C++ для суффикса trie, но я хочу, чтобы этот код отслеживал счетчики на каждом узле, как часто появляется символ или подстрока во время суффикса trie construction: учитывая что я работаю только с 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

проблема заключается в том, что его конструкция является некорректной для поиска и insert: вы делаете это для одиночных символов, а trie должны работать со строкой.

Анализ проблемы

Если вы распечатайте синтаксическое дерево, вы увидите, что вы строите дерево расширяющегося ветвь, соответствующую тоже букву. Вы сделали это, потому что вы вставляете одну букву в то время, но это не обычный макет из синтаксического дерева:

Аналогично, при поиске элемента, если это корневой элемент, все ОК. Но если это не корневой элемент, ваш код всегда будет искать ветвь, соответствующую текущему узлу, и это рекурсивно, что означает, что он будет искать только в ветви, соответствующей корню.

Первый шаг на пути решения: исправить код

Если вы хотите найти любую букву в структуре 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; 

} 

И я получаю следующий результат: Не найдено

Это сбивает с толку, так как аб находится в ст кольцо s.

И, наконец, я пытаюсь понять эту строку:

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

означает ли это, мы получаем код ASCII для «а», а затем вычесть из ASCII код текущего символа?

Спасибо