KMP N번 수행해서 O(N^2) DP를 했던 것 같네요.

문자열 최대길이는 5000이였나요~?

좀더 자세히 설명해주시면 감사하겠습니다 .. 

D(i)를 1~i번째 문자열에 대한 답이라고 하면, D(i) = min(D(j) + F(j+1 ~ i)) (j < i)였나 이런식이었던 것 같아요.

F(j+1 ~ i)는 문자열 S(j+1 ~ i)의 prefix와 suffix가 같은 길이를 L이라 했을 때에 L이 조건을 만족하면 1, 아니면 0이었나... 아니면 L자체였나...

문제 자체가 잘 기억이 안나지만 대충 이런 식이었던 것 같아요.

저 F를 계산을 미리 해두기 위해서 S(1~N)에 대해 KMP의 Pi배열을 구해놓고, S(2~N)에 대해 Pi 배열을 구해놓고, .... N번 KMP 돌렸어요.

답변 감사합니다.