Dynamic programming: longest common substring and longest common subsequence

The longest public substring

Given two strings , Find the longest identical substring , For example, stator string asdfas and werasdfaswer, The longest substring shared by the two substrings is asdfas This string .
Again , At first glance, this problem is dynamic programming , We first list the state transition equation , Suppose two strings are separated by i,j The length of the longest common substring at the end is dp[i][j], When A[i]==B[j] when ,dp[i][j]=dp[i-1][j-1]+1, If these two characters are not equal , That is to say A[i],B[j] The two strings ending with are not common substrings , here dp[i][j]=0

a	s	d	f	a	s
w	e	r	a	s	d	f	a	s	w

s1 = input()
s2 = input()

n1 = len(s1)
n2 = len(s2)

dp = [[0 for _ in range(n2)] for _ in range(n1)]
max_len = 0
for i,x in enumerate(s1):
    for j,y in enumerate(s2):
        if x == y:
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1] + 1
        if dp[i][j] > max_len:
            max_len = dp[i][j]
print(max_len)

Longest common subsequence

Common subsequences do not need to be continuous , therefore , Even if two strings are not equal ,dp[i][j] Not for 0. The current two characters are not equal ,t1[i]!=t2[j] Words , Then the minimum length is also dp[i-1][j-1], But that's not enough , Because we want to get as much length as possible in the previous comparison . Then when the current characters are not equal , You should put the current character into the previous comparison , Then there must be dp[i][j-1] and dp[i-1][j]>=dp[i][j]. Simply speaking ,dp[i][j] The value of should be from dp[i-1][j-1],dp[i][j-1],dp[i-1][j] Choose from the three , but dp[i][j]≤ The other two , So compare the other two , Take the larger .

The state representation we define f Array and text Array subscripts are from 1 At the beginning , And the title gives text Array subscript is from 0 At the beginning , For one A corresponding , In judging text1 and text2 When the last bit of the array is equal , One wrong place forward , That is to use text1[i - 1] and text2[j - 1] To judge .

Here's why f Array and text Arrays are defined as subscripts from 1 Start . The reason is because of the state transition equation f[i][j] = max(f[i - 1][j],f[i][j - 1]), When our f Array defined as subscript from 1 After the start , We can make no extra judgment on the problem of subscript out of bounds in the code . In fact, we can also find a problem , Is the original array given by the topic , such as text Array , If subscript from 1 At the beginning , The state representation will be clearer , The process of deriving the state transition equation will also be better understood .

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return dp[m][n]