*
/ \ \
a b c
/ \
b c
/
c
prints *a*
comes to b, appends a with b prints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal <[email protected]>wrote:
> But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
>
> On Wed, Jul 27, 2011 at 12:39 PM, surender sanke <[email protected]>wrote:
>
>>
>>
>> @sunny
>> consider *uncompressed* suffix tree, even with distinct elements maximum
>> number of nodes with string length n formed will be 2n.
>> once suffix tree is constructed, needs to traverse in dfs order appending
>> the node found on the way.
>> total complexity would be O(construction of suffix tree ) + O(traverse
>> time).
>>
>> surender
>>
>>
>> On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
>> <[email protected]>wrote:
>>
>>> @shiva viknesh
>>> this is a different Question.......
>>>
>>> @saurabh
>>> how is nlgn possible, total no of possible substrings are n^2
>>>
>>>
>>> this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh
>>>
>>> for(int l = 0; l < len; l++){
>>> for(int i = 0; i < len-l; i++){
>>> int j = i+l;
>>> char temp = s[j+1];
>>> s[j+1] = 0;
>>> printf("%s\n", s+i);
>>> s[j+1] = temp;
>>> }
>>> }
>>>
>>> <[email protected]> wrote:
>>> >
>>> > using suffix tree this can be done in o(nlogn) though will take extra
>>> space.
>>> >
>>> > On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh <[email protected]>
>>> wrote:
>>> >>
>>> >> http://geeksforgeeks.org/?p=767
>>> >>
>>> >> On Jul 26, 11:49 pm, Pratz mary <[email protected]> wrote:
>>> >> > how?
>>> >> >
>>> >> > On 26 July 2011 23:18, ankit sambyal <[email protected]>
>>> wrote:
>>> >> >
>>> >> > > @vivin : Suffix trees are memory intensive..
>>> >> >
>>> >> > > This problem can be solved just by running 2 nested loops in O(1)
>>> >> > > space and O(n^2) time
>>> >> >
>>> >> > > --
>>> >> > > You received this message because you are subscribed to the Google
>>> Groups
>>> >> > > "Algorithm Geeks" group.
>>> >> > > To post to this group, send email to [email protected].
>>> >> > > To unsubscribe from this group, send email to
>>> >> > > [email protected].
>>> >> > > For more options, visit this group at
>>> >> > >http://groups.google.com/group/algogeeks?hl=en.
>>> >> >
>>> >> > --
>>> >> > regards Pratima :)
>>> >>
>>> >> --
>>> >> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> >> To post to this group, send email to [email protected].
>>> >> To unsubscribe from this group, send email to
>>> [email protected].
>>> >> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>> >>
>>> >
>>> >
>>> >
>>> > --
>>> > Saurabh Singh
>>> > B.Tech (Computer Science)
>>> > MNNIT ALLAHABAD
>>> >
>>> >
>>> > --
>>> > You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> > To post to this group, send email to [email protected].
>>> > To unsubscribe from this group, send email to
>>> [email protected].
>>> > For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>>
>>> --
>>> Sunny Aggrawal
>>> B-Tech IV year,CSI
>>> Indian Institute Of Technology,Roorkee
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
