Проблема с указателем при реализации дерева суффиксов в переполнении стека
Я пытался реализовать дерево суффиксов с помощью c ++, посмотрев несколько примеров в Интернете. Я столкнулся с проблемой указателя, и я не могу исправить это. Любая помощь с благодарностью.
/*
* Implement suffix array to print the maximum suffix substring in a string
* Algorithm:
* Build a suffix tree and find the lowest node with multiple children
*
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <ctype.h>
using namespace std;
struct node{
char ch;
node* next[26];
int treeHeight;
int childCount;
int end = 0;
};
void insertSuffixIntoTree(node*& root, string suffix){
if (suffix.size() == 0){
return;
}
char c = suffix[0];
int index = tolower(c) - 'a';
if (root->next[index] == NULL){
root->next[index] = new node();
for (int k = 0; k < 26; k++){
root->next[index]->next[k] = NULL;
}
root->next[index]->ch = tolower(c);
if (suffix.size() == 1){
root->next[index]->end = 1;
}
}
suffix.erase(suffix.begin());
insertSuffixIntoTree(root->next[index], suffix);
}
void buildSuffixTree(node* root, string str){
if (root == NULL) cout << "CRAP" << endl;
for (int i = str.size() - 1; i >= 0; i--){
string suffix = str.substr(i);
cout << "suffix is " << suffix << endl;
insertSuffixIntoTree(root, suffix);
}
}void printSuffixTree(node* root, string str){
if (root->end){
cout << str << endl;
return;
}
for (int i = 0; i<26; i++){
while (root->next[i]){
str += root->ch;
return printSuffixTree(root->next[i],str);
}
}
}
int main() {
string str;
node* suffixRoot = new node();
suffixRoot->ch = ' ';
for (int i = 0; i < 26; i++){
suffixRoot->next[i] = NULL;
}
cout << "enter the string" << endl;
cin >> str;
buildSuffixTree(suffixRoot, str);
//string result = findMaxSuffix(suffixRoot,str);
//cout<<"result is "<<result<<endl;
string result = "";
printSuffixTree(suffixRoot,result);
getchar();
return 0;
}
Ошибка происходит в методе insertIntoSuffixTree внутри метода buildSuffixTree. Насколько я понимаю, я теряю адрес указателя, с которого я начал. Есть идеи, как обойти эту проблему?
Решение
Приносим извинения за доставленные неудобства. Я исправил код, как показано ниже:
/*
* Implement suffix array to print the maximum suffix substring in a string
* Algorithm:
* Build a suffix tree and find the lowest node with multiple children
*
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <ctype.h>
using namespace std;
struct node{
char ch;
node* next[26];
int treeHeight;
int childCount;
int end = 0;
};
void insertSuffixIntoTree(node* root, string suffix){
if (suffix.size() == 0){
return;
}
char c = suffix[0];
int index = tolower(c) - 'a';
if (root->next[index] == NULL){
root->next[index] = new node();
for (int k = 0; k < 26; k++){
root->next[index]->next[k] = NULL;
}
root->next[index]->ch = tolower(c);
if (suffix.size() == 1){
root->next[index]->end = 1;
}
}
suffix.erase(suffix.begin());
insertSuffixIntoTree(root->next[index], suffix);
}
void buildSuffixTree(node* root, string str){
if (root == NULL) cout << "CRAP" << endl;
for (int i = str.size() - 1; i >= 0; i--){
string suffix = str.substr(i);
cout << "suffix is " << suffix << endl;
insertSuffixIntoTree(root, suffix);
}
}
bool checkEmptyVector(node * leaf){
for (int i = 0; i < 26; i++){
if (leaf->next[i] != NULL){
return false;
}
}
return true;
}
void printSuffixTree(node* root, string str){
if (root->end){
cout << str << endl;
}
if (checkEmptyVector(root)){
return;
}
for (int i = 0; i<26; i++){
//cout << "inside for loop, i is " << i << endl;
while (root->next[i]){
str += root->next[i]->ch;
printSuffixTree(root->next[i],str);
break;
}
}
}
int main() {
string str;
node* suffixRoot = new node();
suffixRoot->ch = ' ';
for (int i = 0; i < 26; i++){
suffixRoot->next[i] = NULL;
}
cout << "enter the string" << endl;
cin >> str;
buildSuffixTree(suffixRoot, str);
//string result = findMaxSuffix(suffixRoot,str);
//cout<<"result is "<<result<<endl;
string result = "";
printSuffixTree(suffixRoot,result);
getchar();
return 0;
}
Другие решения
Других решений пока нет …