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 <[email protected]> wrote: > @ sunny , ur right!! > > surender > > On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal <[email protected]>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 <[email protected]>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 <[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. >>> >> >> >> >> -- >> 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. > -- 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.
