Skiena's Algorithm Design Manual Question 8-3 part b asks to give a "simpler" BigO(nm) algorithm for finding the longest common substring that does not rely on dynamic programming. The obvious answer seems to be to use a suffix tree, however, Skiena uses the word "Simpler" I am not sure suffix trees are simpler than DP, maybe the search is simpler, but building a suffix tree in nm time complexity is anything but simple. So, I'm wondering, is there another way to solve this problem in O(nm) time?
Add a comment
|
1 Answer
Let's says we fixed starting position i in first(shorter) string s. Now Let's find its longest possible prefix in the longer string. It may be done in O(n + m) by examining prefix function(or z function) of string s[i:] + # + t where # is special symbol that doesn't exist in any of s and t.
Overall complexity is O(n(n + m)) which is O(nm) if n < m
