i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !!!!!
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke <surend...@gmail.com> wrote:
> *
> / \ \
> 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
> <sunny816.i...@gmail.com>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 <surend...@gmail.com>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 <sunny816.i...@gmail.com
>>> > 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;
>>>> }
>>>> }
>>>>
>>>> <saurab...@gmail.com> 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 <
>>>> sivavikne...@gmail.com> wrote:
>>>> >>
>>>> >> http://geeksforgeeks.org/?p=767
>>>> >>
>>>> >> On Jul 26, 11:49 pm, Pratz mary <pratima.m...@gmail.com> wrote:
>>>> >> > how?
>>>> >> >
>>>> >> > On 26 July 2011 23:18, ankit sambyal <ankitsamb...@gmail.com>
>>>> 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 algogeeks@googlegroups.com.
>>>> >> > > To unsubscribe from this group, send email to
>>>> >> > > algogeeks+unsubscr...@googlegroups.com.
>>>> >> > > 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 algogeeks@googlegroups.com.
>>>> >> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> >> 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 algogeeks@googlegroups.com.
>>>> > To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> > 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 algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> 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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
