Programming Practice: Basic Suffix Tree in C++

gistfile1.cpp

#include <iostream>
#include <cstring>
#include <climits>
using namespace std;

class index_list {
public:
	int value;
	index_list * next;
	index_list(int i) : value(i), next(0) {}
	~index_list() {
		if(next) delete next;
	}
};

// suffix tree implementation
class SuffixTree {
public:
	char value;
	SuffixTree * child[UCHAR_MAX+1];
	index_list * indices;
	SuffixTree() {
		for(int i = 0; i < UCHAR_MAX+1; ++i)
			child[i] = NULL;
		indices = NULL;
	}
	~SuffixTree() {
		for(int i = 0; i < UCHAR_MAX+1; ++i) 
			if(child[i])
				delete child[i];
		delete indices;
	}
	void insert(const char * s, int i) {
		// add i to the index list
		if(indices)	
			indices->next = new index_list(i);
		else 
			indices = new index_list(i);
		// add child for the character s[0], recurse
		if(strlen(s) > 0) {
			value = s[0];
			SuffixTree * c = NULL;
			if(child[value]) {
				c = child[value];
			} else {
				c = new SuffixTree();
				child[value] = c;
			}
			child[value]->insert(s+1, i);
		}
	}
	index_list * search(const char * s) {
		if(strlen(s) <= 0)
			return indices;
		else if(child[s[0]]) 
			return child[s[0]]->search(s+1);
		return NULL;
	}
};

void insert(SuffixTree & root, const char * s) {
	const size_t len = strlen(s); 
	for(int i = 0; i < len; ++i) 
		root.insert(s+i, i);
}

int main() {
	SuffixTree t;
	insert(t, "hello");

	index_list * results = t.search("l");
	if(results) {
		cout << "found string at indices: ";
		while(results) {
			cout << results->value << " ";
			results = results->next;
		}
		cout << endl;
	} else {
		cout << "did not find substring." << endl;
	}
	return 0;
}