Discussion @ 1393. Average Common Prefix @ Timus Online Judge

To Admin: more memory please Einstein Chen(einstein[underline]csm[at]hotmail[dot]com) 9 Mar 2006 07:37

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...

Re: To Admin: more memory please Kit 10 Mar 2006 22:19

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

Re: To Admin: more memory please GaLL[Tyumen SU] 10 Mar 2006 23:51

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

Hint (+) Grebnov Ilya[Ivanovo SPU] 11 Mar 2006 14:27

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

Re: Hint (+) Alias (Alexander Prudaev) 18 Mar 2007 21:39

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

Re: Hint (+) Ilya Grebnov[Ivanovo SPU] 19 Mar 2007 10:56

Edited by author 25.11.2007 16:05

Edited by author 25.11.2007 16:05

Re: Hint (+) Alias (Alexander Prudaev) 19 Mar 2007 15:27

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

Re: To Admin: more memory please Einstein Chen(einstein[underline]csm[at]hotmail[dot]com) 11 Mar 2006 15:03

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

Re: To Admin: more memory please Kit 11 Mar 2006 16:16

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

All the dirty account found will be deleted soon. Enjoy the last days of freedom :) (-) Dmitry 'Diman_YES' Kovalioff 11 Mar 2006 17:01

No subject Einstein Chen(einstein[underline]csm[at]hotmail[dot]com) 11 Mar 2006 18:12

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

Discussion of Problem 1393. Average Common Prefix