only suffix tree is the soln i think..
On Wed, Sep 2, 2009 at 11:20 AM, nitin mathur <nitinkumar.mat...@gmail.com>wrote: > Hi everybody.. > > I am sorry as the algorithm I proposed takes O(n^2) and not O(n). But its > not wrong. > > @Ankur The algorithm given in cormen is for longest common > subsequence. But a similar algorithm exists for longest common substring > too. > > you can find it following the link > http://en.wikipedia.org/wiki/Longest_common_substring_problem > > <http://en.wikipedia.org/wiki/Longest_common_substring_problem>Actually > these problems (that uses Dynamic Programming approach) are solved in two > stages. First, we need to build a table and then we need to traverse it in > particular fashion to retrieve all possible longest common substrings. > > The second stage takes O(n) time. > But the preprocessing takes O(n^2) time. > So, overall it takes O(n^2) time. > > I believe its worst approach for this problem (as it needs O(n^2) extra > spaces too). So not needed to discuss more about this approach. Better some > other method should be discovered. > > > > Nitin Mathur > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
