suffix tree

Longest Common Substring

Given two strings, find the longest common substring.

Return the length of it.

Example

Given A ="ABCD", B ="CBCE", return2.

Method 1: DP (N*M time, N*M space)

• Define dp[i][j] == length of common substring from A[0:i] and B[0:j]
• Since we are traversing from the beginning of the string, we can check the previous value dp[i-1][j-1] to know if there is already a common substring at A[0:0-1] and B[0:j-1], and we just increment that value by 1.
• if either i or j is 0, that means we can't check its previous value, so we just set it to 1.
• every time we found a match, we compare the current matched length to a global longest variable, and update it if necessary.

class Solution:
    """
    @param: A: A string
    @param: B: A string
    @return: the length of the longest common substring.
    """
    def longestCommonSubstring(self, A, B):
        # write your code here
        dp = [[0 for i in xrange(len(B))] for j in xrange(len(A))] 
        result = 0

        for i in xrange(len(A)):
            for j in xrange(len(B)):
                if A[i] == B[j]:
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i-1][j-1] + 1
                    result = max(result, dp[i][j])
        return result