Суффикс Три в переполнении стека

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";
}

3

c++suffix-tree

Решение

Другие решения

@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 находится в строке s.

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

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

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

Спасибо

0

Источник

Accepted Answer

Проблема в том, что его дизайн имеет недостатки для поиска и вставки: вы делаете это для отдельных символов, в то время как 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);
}

Это исправляет код, а не основной дизайн. Здесь онлайн демо здесь.

Но для исправления дизайна необходима дальнейшая работа

Дизайн должен вставлять / искать строку s, Идея состоит в том, чтобы проверить текущий символ с s[0] и рекурсивно вставить / найти оставшуюся строку s.substr(1);

2