Pointer issue while implementing suffix tree in c++

Question

I was trying to implement suffix tree using c++ by looking at some examples online. I am running into pointer issue and I am not able to fix it. Any help is greatly appreciated.

/*
* 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;
}

The error is happening at insertIntoSuffixTree method inside buildSuffixTree method. My understanding is I am loosing my pointer address I started with. Any idea on how to get around this issue?

What makes you think you're "losing your pointer address" ? Did you run this in a debugger and see an unexpected value residing in one of your `node` pointers ? You said "The error is happening at `insertIntoSuffixTree` method" - *What error* ? Always post any error messaging as part of your question. — WhozCraig, Jul 08 '16 at 05:53
I was not losing the pointer address. I was getting different starting address for every suffix which was getting added. That was the error. I figured out the error and fixed it myself. I was thinking I needed to use double pointer or something like that but turned out it was much easier than that. Attaching corrected code below, don't know if any one will look at it though :) — sri_84, Jul 08 '16 at 06:14
[using namespace std; bad idea](http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-in-c-considered-bad-practice) — Ed Heal, Jul 08 '16 at 06:20

score 0 · Answer 1 · answered Jul 08 '16 at 06:15

Sorry for any inconvenience. I fixed the code as seen below:

/*
* 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;
}

Pointer issue while implementing suffix tree in c++

1 Answers1