Longest Common Substring

Question

Given two strings, find the longest common substring.

Return the length of it.

Example Given A = "ABCD", B = "CBCE", return 2.

Thoughts

创建一个dp[i][j], dp[i][j]表示a的前i个和b的前j个的lcs, 创建长度+1的，dp[1][1]对应A[0]和B[0]

init states: dp[0][0] = 0

Connection function:

if A[i-1] == B[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1

final result: dp[0-i][0-j]中的最大值

Solution

class Solution:
    # @param A, B: Two string.
    # @return: the length of the longest common substring.
    def longestCommonSubstring(self, A, B):
        # write your code here
        if not A or not B:       
            return 0  
        max = 0
        dp = [[0 for j in range(len(B)+1)] for i in range(len(A)+1)]
        for i in range(1, len(A)+1):  
            for j in range(1, len(B)+1):                         
                    if A[i-1] == B[j-1]:                        
                        dp[i][j] = dp[i-1][j-1] + 1   
                        if dp[i][j] > max:
                            max = dp[i][j]
                    else:        
                        dp[i][j] = 0 
        return max