[백준] 5582. 공통 부분 문자열 풀이 (Python, TypeScript)

5582번: 공통 부분 문자열

접근한 방법

최장 공통 부분수열을 구하는 문제로써 DP를 활용하여 해결할 수 있습니다.

1. DP 테이블 d를 생성하여 문자열의 길이에 따른 최장 공통 부분 수열 길이를 저장합니다. d[i][j]는 s1의 첫 i개 문자와 s2의 첫 j개 문자 사이에서의 최대 공통 부분 수열의 길이를 나타냅니다.

2. 문자열을 비교해 최장 공통 부분 수열 길이를 갱신합니다. 이중 반복문을 사용하여 s1과 s2의 각 문자를 순회하면서 만약 s1[i - 1]과 s2[j - 1]이 같은 문자라면, 현재 위치의 d 값을 왼쪽 위 대각선의 값 d[i - 1][j - 1]에 1을 더한 값으로 갱신합니다. 새로운 문자가 공통 부분 수열에 추가되기 때문입니다.

3. 위 방식으로 문자열의 모든 위치를 비교하고 d 배열을 갱신한 후, 현재까지의 최장 공통 부분 수열의 길이를 계속 갱신합니다. 최종  result에는 두 문자열 사이의 최장 공통 부분 수열의 길이가 저장됩니다. 

 

Python

import sys
input = sys.stdin.readline

s1, s2 = input().rstrip(), input().rstrip()
d = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
result = 0
for i in range(1, len(s1) + 1):
    for j in range(1, len(s2) + 1):
        if s1[i - 1] == s2[j - 1]:
            d[i][j] = d[i - 1][j - 1] + 1
            result = max(result, d[i][j])
print(result)

TypeScript

function sol5582(s1: string, s2: string) {
  const d = Array.from({ length: s1.length + 1 }, () =>
    Array(s2.length + 1).fill(0)
  );
  let result = 0;
  for (let i = 1; i <= s1.length; i += 1) {
    for (let j = 1; j <= s2.length; j += 1) {
      if (s1[i - 1] === s2[j - 1]) {
        d[i][j] = d[i - 1][j - 1] + 1;
        result = Math.max(result, d[i][j]);
      }
    }
  }
  return result;
}
console.log(sol5582("ABRACADABRA", "ECADADABRBCRDARA"));