최장 공통 부분 문자열(파이썬)

이승수·2022년 10월 12일

알고리즘

문제 설명

두 단어가 있을 때 최장 공통 부분 문자열의 길이를 구하는 프로그램을 작성해 봅시다. 부분 문자열이란 문자열에서 일부분을 잘라낸 것을 말합니다. 파이썬의 슬라이싱과 비슷하다고 생각하시면 됩니다.

문자열 ABCDEFG 을 예로 들면,
ABC, BCDE, FG 등 문자열에서 일부를 잘라낸 모든 예가 부분 문자열이 될 수 있습니다.
공통 부분 문자열은 두 개의 문자열이 있다고 할 때, 이 두 문자열의 부분 문자열 중 일치하는 부분 문자열을 말합니다.

예를 들어 ABCDEF, GBCDFE이라는 두 문자열이 있을 때 공통 부분 문자열은 BCD등이 될 것입니다.

이 중 가장 긴 문자열이 최장 공통 부분 문자열이 됩니다. 이 예시에서는 ABC 최장 공통 부분 문자열이 되며, 따라서 3를 출력하면 됩니다.

입력

두 단어가 공백으로 구분되어 입력됩니다.
각 단어는 알파벳 소문자로만 이루어져 있으며 최대 3000글자입니다.

출력

두 단어 사이의 최대 공통 부분 문자열의 길이를 출력합니다.

풀이

Dynamic Programming

A, B = input().split(" ")

dp = [[0 for _ in range(len(B)+1)] for _ in range(len(A)+1)]

A = [0] + list(A)
B = [0] + list(B)

length = 0

for i in range(1, len(A)):
    for j in range(1, len(B)):
        if A[i] == B[j]:
            dp[i][j] = dp[i-1][j-1] +1
        else:
            dp[i][j] = 0
        length = max(length, dp[i][j])

print(length)