My solution using suffix tree got MLE...

Here is the definition of suffix tree node:

typedef    struct    node    *point;
struct    node
{
    point    ParentLink,SuffixLink;
    point    Child,Brother;
    int    FirstCharIndex,LastCharIndex,Depth;
    int    ID;
}

sizeof(node)=32

A suffix tree of a n-length string has at most 2*n nodes,
so the tree may use 32*2*250000=16MB memory and lead to MLE.
Please RELAX THE MEMORY LIMIT or tell me how to reduce the space requirement of suffix tree.
Thanks...

I used suffix tree also and there is enough memory. But, as you notice, it is quite difficult...

You can use bit fields:

struct node
{
point ParentLink,SuffixLink;
point Child,Brother;
int FirstCharIndex:24,LastCharIndex:24,Depth:24;
int ID:24;
}

sizeof(node)=28

Problem can be easy solved without Suffix Tree. Try Suffix Array. Suffix array can be easy constructed in O(N*ln(N)*ln(N)) time with 8*N bytes addition memory.

See this
http://acm.timus.ru/status.aspx?space=1&num=1393&status=accepted&pos=1021243

Edited by moderator 11.03.2006 16:59

Great thanks to Kit,GaLL[Tyumen SU],Grebnov Ilya[Ivanovo SPU].
After several of MLEs,finally ACed using suffix tree :)

http://acm.timus.ru/status.aspx?space=1&num=1393&status=accepted&pos=1113397

Just for interest, why you use dirty account? I don't blame you, but I don't see reasons for such fraud. Why?

i use it just for fun...
if all of you think that it's a fraud,i will not use it any longer
and sorry

to Grebnov Ilya[Ivanovo SPU] :
i have tried to find information about constructing suffix array
using google, but all information is in english.
please give me some links, or if you can,
please send me your implementation.

Edited by author 18.03.2007 21:39

Edited by author 25.11.2007 16:05

Edited by author 25.11.2007 16:05

by the way, this problem can be solved in O(n) time :)
but a don't know these algorithms