[PS] BOJ 5582 / 공통 부분 문자열

Minjun Kim

17 Jul 2025 • 2 min read

문제 링크: https://www.acmicpc.net/problem/5582

Thumbnail: Photo by Brett Jordan (Unsplash)

LCS(Longest Common Substring) 를 구하는 문제입니다.

풀이

문제 이름 그대로 LCS (Longest Common Subsequence)를 구하는 문제입니다.

Longest Common String, 최장 공통 문자열

LCS 알고리즘은 2차원 배열을 사용해 결과를 계산합니다. 두 문자열 \(A\)와 \(B\)의 길이를 열과 행의 길이로 가지는 2차원 배열 LCS를 정의합니다. (행과 열의 순서가 바뀌어도 상관없습니다.)

input = open(0).readline
A = input().strip()
B = input().strip()
a_length = len(A)
b_length = len(B)

LCS = [[0 for _ in range(a_length + 1)] for _ in range(b_length + 1)]

LCS 2차원 배열 선언

이때, 배열의 0번 행과 열은 계산의 편의를 위해 마진으로 0을 채워넣습니다.

이제 점화식을 사용해 LCS배열을 채우면 됩니다.

for b_idx in range(1, b_length + 1):
    for a_idx in range(1, a_length + 1):
        if A[a_idx - 1] == B[b_idx - 1]: # 현재 비교하는 두 글자가 같다면
            LCS[b_idx][a_idx] = LCS[b_idx - 1][a_idx - 1] + 1 # LCS 값 갱신
        else:
            LCS[b_idx][a_idx] = 0

LCS(Longest Common Substring)의 점화식

보다 자세한 설명은 이전 글을 참고해 주세요!

전체 코드

input = open(0).readline
A = input().strip()
B = input().strip()
a_length = len(A)
b_length = len(B)

LCS = [[0] * (a_length + 1) for _ in range(b_length + 1)]
max_lcs = 0
for b_i in range(1, b_length + 1):
    for a_i in range(1, a_length + 1):
        if A[a_i - 1] == B[b_i - 1]:
            LCS[b_i][a_i] = LCS[b_i - 1][a_i - 1] + 1
            max_lcs = max(max_lcs, LCS[b_i][a_i])
        else:
            LCS[b_i][a_i] = 0

print(max_lcs)

solution.py