[알고리즘] Maximum Length of Repeated Subarray

포인트

• LCS 를 물어보는 문제입니다. LCS 도 2가지 종류가 있습니다. 1. Longest Common Substring 과 2. Longest Common Subsequence 입니다. 
• 1. Longest Common Substring 는 최장 공통 문자열로 '연속된' 공통 문자에 관한 것입니다.
• 2. Longest Common Subsequence 는 부분 수열중 최장의 길이를 나타내는 것입니다. 
  2개다 연관이 되어 있으나 점화식은 다를 수 있으니 주의하시기 바랍니다.

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

예시) [0,0,0,0,0], [0,0,0,0,0]

[0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1]
[0, 1, 2, 2, 2, 2]
[0, 1, 2, 3, 3, 3]
[0, 1, 2, 3, 4, 4]
[0, 1, 2, 3, 4, 5]

결과로 5가 최댓값을 가짐으로 이 문제에서 최장 공통 문자열의 길이는 5입니다. 

python

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.insert(0, 0)
        nums2.insert(0, 0)
        d = [[0] * len(nums1) for _ in range(len(nums2))]
        value = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                if i == 0 or j == 0:
                    d[i][j] = 0
                elif nums1[i] == nums2[j]:
                    d[i][j] = d[i - 1][j - 1] + 1
                else:
                    d[i][j] = 0
                value = max(value, d[i][j])

        return value