Find the longest sub string that occurs more than once.

longestdupsubstring.cpp

class trie_node {
public:
    trie_node* child[256];
    trie_node() {
        for(int i=1; i<256; ++i)
            child[i] = NULL;
    };
};

// return value is the length of the dup sub string
int insert(trie_node* root, const char* str)
{
    if(!str) return 0;
    int len = 0;
    while(*str != '\0') {
        if(root->child[*str] != NULL) {
            // dup string extended, increase length by 1
            len++;
        }
        else {
            // no dup string found, creating node trie_node
            root->child[*str] = new trie_node;
        }

        root = root->child[*str];
        str++;
    }
    return len;
}

void longestDupSubstr(const char* str) {
    if(!str) return;
    trie_node* root = new trie_node;
    int maxLen=0;
    const char *start;
    // loop through the string to insert all suffix into the trie
    while(*str != '\0') {
        int len;
        len = insert(root, str);
        if(maxLen < len) {
            maxLen = len;
            start = str;
        }
        str++;
    }

    if(maxLen==0) {
        cout << "no dup substring found\n";
        return;
    }

    cout << maxLen << endl;
    while(maxLen-- > 0)
        cout << *(start++);
    cout << endl;
    return;
}