this has been discussed here before and if i remeber correctly the solution was O(nlogn). Please go through the archives.
On Thu, Aug 26, 2010 at 12:20 PM, Aditya Shanker <[email protected]>wrote: > The question would be complete if we know what order of notation is needed > for solution. > > > On 23.08.2010 15:32, Chi Hoang wrote: > > I don't think so, I've have wriiten a kart-trie: > http://sourceforge.net/projects/kart-trie which is basically a > patricia-tree or radix-tree. Such a tree has maximum 2 leafs at each branch > whilst a suffix-tree can has more then 2 leafs at each branch (BTW. can you > explain to me what does edge means when talking about trees?). This is my > understanding of a suffix-tree so far. I'm awaiting your anwser! > 2010/8/21 Chonku <[email protected]> > >> You use a trie when you want to model a number of strings. Suffix Tree is >> used only when you have one string in your model. Suffix Tree is a type of >> trie, but the difference lies in the intent. >> >> >> On Sat, Aug 21, 2010 at 7:22 PM, Chi <[email protected]> wrote: >> >>> Isn't that by definition a compressed trie, i.e patricia-tree, crit- >>> bit tree (suffix-tree)? Or what is the difference? >>> >>> On Aug 20, 5:17 pm, Nikhil Jindal <[email protected]> wrote: >>> > @chonku >>> > As i understand, a trie is used when we have a lot of strings (such as >>> a >>> > dictionary). >>> > Here we just have a single string. The resultant trie will be: >>> > >>> > a >>> > \ >>> > b >>> > \ >>> > c >>> > \ >>> > l >>> > \ >>> > e >>> > \ >>> > v >>> > \ >>> > e >>> > \ >>> > l >>> > \ >>> > a >>> > \ >>> > b >>> > \ >>> > c >>> > >>> > We get a similar trie for the reverse string. >>> > >>> > So why are you using a trie here? I cant see any advantage of it here. >>> > >>> > >>> > >>> > >>> > >>> > On Fri, Aug 20, 2010 at 8:36 AM, Chonku <[email protected]> wrote: >>> > > Can we use a trie here. >>> > > Make first pass from left to right and construct the trie. >>> > > Make second pass from right to left and look for the trie branch with >>> > > maximum nodes that match the characters. >>> > >>> > > On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal < >>> [email protected]>wrote: >>> > >>> > >> Hi All, >>> > >>> > >> Givan a string, you have to find the longest palindromic substring. >>> > >> For ex: Longest Palindromic substring for abclevelabc is level. >>> > >>> > >> What is the most optimised solution possible? >>> > >>> > >> Please access the attached hyperlink for an important electronic >>> communications disclaimer: >>> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php >>> > >>> > >> -- >>> > >>> > >> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> > >>> > >> To post to this group, send email [email protected]. >>> > >>> > >> To unsubscribe from this group, send email >>> [email protected]<toalgogeeks%[email protected]> >>> <algogeeks%[email protected]<algogeeks%[email protected]> >>> >. >>> > >>> > >> For more options, visit this group athttp:// >>> 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 >>> [email protected]. >>> > > To unsubscribe from this group, send email to> >>> [email protected]<algogeeks%[email protected]><algogeeks%2bunsubscr...@googlegroups >>> .com> <algogeeks%[email protected]> >>> > > . >>> > > For more options, visit this group at >>> > >http://groups.google.com/group/algogeeks?hl=en. >>> > >>> > Please access the attached hyperlink for an important electronic >>> communications disclaimer: >>> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php >>> >>> -- >>> 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]<algogeeks%[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]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > ...::: Chi Hoang :::... > Freelancer/PHP/TYPO3/MySQL > Tel: +49(0)221-9460023 > Url1: http://www.chihoang.de > Url2: http://nano-math.users.sourceforge.net > e-Mail: info at chihoang.de > Skype: tetramatrix > -- > 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]<algogeeks%[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.
