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