Longest Common Substring

Question

• lintcode: (79) Longest Common Substring

Given two strings, find the longest common substring.
Return the length of it.

Example
Given A="ABCD", B="CBCE", return 2.
Note
The characters in substring should occur continuously in original string.
This is different with subsequence.

题解

• reference

class Solution:
    # @param A, B: Two string.
    # @return: the length of the longest common substring.
    def longestCommonSubstring(self, A, B):
        # write your code here
        ans = 0
        for i in xrange(len(A)):
            for j in xrange(len(B)):
                l = 0
                while i + l < len(A) and j + l < len(B) \
                    and A[i + l] == B[j + l]:
                    l += 1
                if l > ans:
                    ans = l
        return ans

复杂度分析

双重 for 循环，最坏时间复杂度约为 $$O(mn \cdot lcs)$$.