🦊 공통 부분 문자열

1. 문제 링크

공통 부분 문자열

2. 코드

a = input()
b = input()
len_a = len(a);
len_b = len(b);

dp = []
for i in range(len_a + 1):
    dp.append([0] * (len_b + 1));

max_result = 0
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
        max_result = max(max_result, dp[i][j])
print(max_result)

Pypy3 236497KB 448ms

3. 해설

• 해설

  2차원 배열에 i - 1, j -1 번 인덱스는 이전까지 일치했던 개수를 의미함

  이를 찾아가며 최장 부분 수열이 되는지 확인