문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

# 5582
import sys
input = lambda: sys.stdin.readline().strip()

string_a = list(input())
string_b = list(input())

len_a, len_b = len(string_a), len(string_b)

dp = [[0] * (len_b + 1) for _ in range(len_a + 1)]

for i in range(len_a+1):
    for j in range(len_b+1):
        if i == 0 or j == 0:
            dp[i][j] = 0
        elif string_a[i-1] == string_b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = 0
            
len_lcs = 0
for d in dp:
    len_lcs = max(len_lcs, max(d))
    
print(len_lcs)

공통 부분 문자열 출력하는 프로그램

import sys
input = lambda: sys.stdin.readline().strip()

string_a = list(input())
string_b = list(input())

len_a, len_b = len(string_a), len(string_b)

dp = [[0] * (len_b + 1) for _ in range(len_a + 1)]

for i in range(len_a+1):
    for j in range(len_b+1):
        if i == 0 or j == 0:
            dp[i][j] = 0
        elif string_a[i-1] == string_b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = 0
            
len_lcs = 0
a, b = 0, 0
for i in range(len_a+1):
    for j in range(len_b+1):
        if dp[i][j] > len_lcs:
            len_lcs = dp[i][j]
            a, b = i, j
    
print(len_lcs)
if len_lcs == 0:
    exit(0)

output = []
while dp[a][b] > 0:
    output.append(string_a[a-1])
    a, b = a-1, b-1
    
for o in output[::-1]:
    print(o, end = "")

백준 5582 공통 부분 문자열