백준 2401번 최대 문자열 붙여넣기

문제

어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질때 이때 짧은 문자열을 긴 문자열에 붙여 넣을때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차 할 수 없다. (‘aabbc'  에  'aab' 와 'bbc' 둘 다 붙여 넣는 것은 불가능하다.) 또, 짧은 문자열은 여러 번 사용할 수 있다.

문제풀이

사용한 알고리즘 : KMP, DP
algoshipda 님의 코드를 참고하여 작성하였습니다.

(0) 주의 ( 제가 굉장히 많이 실패한 방법 )

 미리 짧은 문자열에 대해 긴 문자열의 어디부터 붙여 넣을 수 있는지 찾아 저장해 놓고 DP 를 돌릴 경우 메모리가 초과 되더라고요....
 메모리 제한이 128MB ( int 32*10^6 개 ) 인데, 최악의 경우 저장해야 하는 integer 가
 (긴 문자열 각 지점(길이)) * (지점 별로 짧은 문자열이 다 들어가면) = 10^5 * 500 > 32*10^6 가 됩니다...
 저는 아직 이 방법으로 푸는 법을 해결하지 못하였습니다.

(1) 코드 9~10

 ' dp[x] : 긴 문자열의 x 글자까지 넣을 수 있는 짧은 문자열의 총 길이의 최대 ' 로 설정하였습니다. 구하고자 하는 건 dp[L-1] 이겠죠. ( L : 긴 문자열 길이 )

(2) 코드 11~16

 보통 KMP 돌릴 때, 긴 문자열을 0~L-1 탐색하면서, 하나의 짧은 문자열이 몇 개나 들어갈 수 있는지 봅니다.
 이 문제에서는 0~L-1 탐색하면서 500개의 짧은 문자열을 한번에 탐색 할 것입니다.
 따라서 각 짧은 문자열의 탐색이 어디까지 되었는지 저장할 행렬이 하나 필요합니다.
 이를 memory 라고 이름 붙여주었습니다.

(3) 코드 26~31

 각 짧은 문자열의 fail 함수를 만들어줍니다.

(4) 코드 34~50

 긴 문자열을 0~ L-1 순서로 탐색하며 dp[0] 부터 dp[L-1] 까지 차례로 만들어줍니다.

 1. 0~i 까지에는 0~i-1 까지에 넣을 수 있는 짧은 문자열을 그대로 넣을 수 있습니다.
 2. N 개의 짧은 문자열을 한번에 탐색할 것입니다. 따라서 과정 (3) 에서 만들어 놓은 memory 라는 행렬을 이용하여 전에 어디까지 탐색하였는지 저장하며 진행합니다.
 3. 만약 어떤 짧은 문자열을 넣을 수 있다면 dp 값을 최신화 해줍니다.