백준 5582번 공통 부분 문자열

< 백준 5582번 공통 부분 문자열 - 마포 코딩박 >

사용한 알고리즘: DP


 두 문자열 A,B 의 공통 부분 문자열 (연속해야함) 의 길이를 구하는 문제입니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~9)
 '연속된' 공통 문자열을 구해야 하므로
 'dp[0][x][y]: 시작안함, A의 x, B의 y 부터 만들 수 있는 최대 공통 부분 문자열 길이'
 'dp[1][x][y]: 시작함(연속되야함), A의 x, B의 y 에서 연속해서 만들 수 있는 최대 공통 부분 문자열 길이' 로 설정하였습니다.

(2) (코드 11~29)
 과정(1)에서 설정한 dp의 값을 구하는 함수를 만들었습니다.
 시작되었는지(연속되어야 하는지) 여부를 판단하며 만들 수 있는 최대 공통 부분 문자열 길이를 dp로 저장해 가며 탐색했습니다.