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 -~----------~----~----~----~------~----~------~--~---
