CODEWITHSUNDEEP
c++algorithmlongest-substring
Jose Villalta
Jose Villalta

Reputation: 1479

Longest Common Substring without Dynamic programming or Suffix Tree

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?

Upvotes: 1

Views: 625

Answers (1)

RiaD
RiaD

Reputation: 47619

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

Upvotes: 1

Related Questions