Find all the unique substring of n strings

This is the problem I am really trying hard to get O(n) solution, but still no success. But in the course of doing same, I came up with nice way of storing all the n strings in a trie, But unfortunately we need to store string starting from each letter till the end to get all the unique sub strings.

#include <string>
#include <iostream>
#include <vector>

const int ALPHABET_SIZE = 26;
char text[2000];
int LEN;
std::vector<std::string> union_unique_strings;

struct trie_node_t { 
    trie_node_t*child_list[ALPHABET_SIZE]; 
    trie_node_t() {
        for(int index = 0; index < ALPHABET_SIZE; index++)
            child_list[index] = (trie_node_t*)0;
    }
};

class Trie {
public:
    Trie():m_root(new trie_node_t) {
    }

    ~Trie() {
        _delete(m_root);
    }

    void _insert(int pos, std::string prefix) {
        int lcv, index; 
        trie_node_t* t = m_root;
        for(lcv = pos; lcv < LEN; lcv++) {
            index = text[lcv] - 'a';
            if (t->child_list[index] == (trie_node_t*)0) { 				
                t->child_list[index] = new trie_node_t;
            }
            t = t->child_list[index];
        }
    }
    void insert() {
        for ( int i = 0; i < LEN; i++) {
            _insert(i, "");
        }
    }

    void iterate() {
        _iterate(m_root, "");
    }

    void _iterate(trie_node_t *t, std::string prefix) {    
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (t->child_list[i] != (trie_node_t*)0) {
                std::string next_prefix = prefix + static_cast<char>('a' + i);
				union_unique_strings.push_back(next_prefix);
                _iterate(t->child_list[i], next_prefix);
            }   
        }
    }   
private:     
    trie_node_t* m_root;
    void _delete (trie_node_t* t) {
        int index; 
        if (t != (trie_node_t*)0) {
            for(index = 0; index < ALPHABET_SIZE; index++)
                _delete(t->child_list[index]);
            delete t;
        }
    }    
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s