Akash johari : can you tell me the way to create suffix tree in o(n) time ? i know only nlogn (also n*logn^2) method . If not , how can you do it in o(n) ?
@ hemeesh : Also how can KMP be useful to solve it ? On Jul 6, 8:25 pm, Hemesh Singh <hemesh.mn...@gmail.com> wrote: > I think this problem can be solved by KMP algorithm in O(n) time. I find > suffix tree hard to implement. > > > > > > > > > > On Tue, Jul 5, 2011 at 9:43 PM, Aakash Johari <aakashj....@gmail.com> wrote: > > Its probably Longest repeating substring problem. So it can be solved with > > suffix array/tree easily in O(n) time. > > > On Tue, Jul 5, 2011 at 9:07 AM, Akshata Sharma > > <akshatasharm...@gmail.com>wrote: > > >> @aakash: see this. I came across this question here > > >>http://geeksforgeeks.org/forum/topic/largest-unique-substring-from-a-... > > >> On Tue, Jul 5, 2011 at 3:15 PM, Aakash Johari <aakashj....@gmail.com>wrote: > > >>> Please make problem clear with example. Longest unique substring is the > >>> string itself, or i have misunderstood the problem. > > >>> On Mon, Jul 4, 2011 at 11:53 PM, Navneet Gupta > >>> <navneetn...@gmail.com>wrote: > > >>>> I think you guys are on different page. There is a difference between > >>>> substring and subsequence. > >>>>http://en.wikipedia.org/wiki/Subsequence#Substring_vs._subsequence > > >>>> This question asks what is the longest SUBSTRING which is unique > >>>> (there could also be none or multiple if lengths are equal) > > >>>> ^Thinking about solution. > > >>>> On Tue, Jul 5, 2011 at 12:20 PM, Azhar Hussain <azhar...@gmail.com> > >>>> wrote: > >>>> > This link can be useful. > >>>> >http://geeksforgeeks.org/?p=12998 > >>>> > - > >>>> > Azhar. > > >>>> > On Tue, Jul 5, 2011 at 11:31 AM, Akshata Sharma < > >>>> akshatasharm...@gmail.com> > >>>> > wrote: > > >>>> >> someone please suggest me an efficient way to find the longest unique > >>>> >> substring in a given string.. > > >>>> >> -- > >>>> >> 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. > > >>>> -- > >>>> Navneet > > >>>> -- > >>>> 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. > > >>> -- > >>> -Aakash Johari > >>> (IIIT 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. > > >> -- > >> 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. > > > -- > > -Aakash Johari > > (IIIT 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. > > -- > Hemesh singh -- 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.
