suffix tree

a very good tutorial in here:

http://www.if-yu.info/2010/10/3/suffix-tree.html (although it is in Chinese)


When string ->> use suffix tree!!

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



struct node
{
    char val;
    bool is_last;
    struct node *child[27];
};

bool insert(node **root, char *word);

int main()
{
    char *str = "abcxxxxxxabc", word[4];
    node *root = NULL;
    int i, len;
    bool flag;

len = strlen(str);
    word[0] = str[0];
    word[1] = str[1];
    word[3] = '\0';
    for(i=2;i<len;++i)
    {
        word[2] = str[i];
        flag = insert(&root, word);
        if(!flag)
        { 
              cout<<"First repeated string is "<<word<<'\n';
              break;
        }
        word[0] = word[1];
        word[1] = word[2];
    }

return 0;
}

bool insert(node **root, char *word)
{
    int i,j;
    node *temp;

if(!(*root))
    {
        *root = new node;
        for(j=0;j<27;++j)
        (*root)->child[j] = NULL;
    }
    //cout<<"new root\n";

temp = *root;

for(i=0;word[i];++i)
    {//cout<<i<<'\n';
    //cin>>nn;
        if(temp->child[word[i]-'a'])
        {
            if(i==2)
            return false;
            temp = temp->child[word[i]-'a'];
        }
        else
        {
            temp->child[word[i]-'a'] = new node;
            temp = temp->child[word[i]-'a'];
            temp->is_last = false;
            for(j=0;j<27;++j)
            temp->child[j] = NULL;
        }
    }

temp->is_last = true;

return true;
}