in the above example y ac is not included in the substring?
On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh <saurab...@gmail.com> wrote:
> hmm o(nlogn) was for constructing the tree.Btw sorry for being unclear.
> The best solution is the obvious one in this case.
>
>
> On Wed, Jul 27, 2011 at 2:10 PM, surender sanke <surend...@gmail.com>wrote:
>
>> @ sunny , ur right!!
>>
>> surender
>>
>> On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal
>> <sunny816.i...@gmail.com>wrote:
>>
>>> 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.
>>>
>>
>> --
>> 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.
>
--
Regards,
Kamakshi
kamakshi...@gmail.com
--
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.
