[백준 5582번] 공통 부분 문자열

난이도: 골드 5

5582번: 공통 부분 문자열

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들

www.acmicpc.net

LCS algorithm을 이용하여 푸는 문제입니다.

다만 이전에 소개했던 longest common substring이 아닌, longest common subsequence의 길이를 구하는 문제입니다.

즉, 연속을 허용하지 않는다는 의미입니다.

자세한 내용은 알고리즘 설명 글에 다루었습니다.

제가 접근한 방법은 아래와 같습니다:

공통 부문 문자열의 최대 길이를 담기 위한 int형 변수 lcs_max를 두고, 0으로 초기화 합니다.
comming string의 길이를 담기 위한 int형 array lcs[][]를 0으로 초기화합니다. 이 크기는 문제에서 주어진 범위 (1~4000)을 이용하여, MAX_N = 4001 이상으로 하였습니다.
문자열의 각 알파벳을 항목별로 비교하여 (subject, target), 같은 경우 lcs의 해당하는 위치에서 값을 1로 설정해 줍니다.
lcs를 쭉 돌아보며, 좌표 (i-1, j-1)의 값이 1 이상인 경우, 좌표 (i, j)에 해당하는 subject, target의 문자가 같을 경우, 좌표 (i,j)에 이전 좌표의 값 + 1을 담습니다.
새로 담은 값과 lcs_max를 비교하여, 더 큰 값을 lcs_max에 담습니다.
탐색이 끝나면 lcs_max를 출력합니다.

연속을 허용하지 않으므로, 구현 난이도는 오히려 더 수월한 편이라고 생각합니다.

코드를 늘 직관적이고 읽기 쉽게 작성하려고 노력하고 있습니다.

혹시나 제 코드 중 의미 전달이 불명확한 경우가 있다면 피드백을 주시면 감사하겠습니다.