http://en.wikipedia.org/wiki/Substring
ac should be a subsequence and not substring.
On Jul 28, 12:00 am, Kamakshii Aggarwal <kamakshi...@gmail.com> wrote:
> 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.
