1787번: 문자열의 주기 예측

1787번: 문자열의 주기 예측 - KMP, DP

문자열이 주어질 때 이 문자열의 모든 접두사에 대하여 추정할 수 있는 주기 중 가장 긴 것의 길이의 합을 출력하는 문제이다.

KMP에서 다뤘던 광고문제나 Slot Machines문제에서 비슷한 유형을 다뤄본 적이 있다.

문자열에서 주기를 구하는 방법은 S - pi[S-1]로 계산하였다.

그러나 이 때의 답은 S-pi[S-1]값이 작을 때였고, 우리가 구해야할 답은 S-pi[S-1]의 값이 클 때가 되어야한다.

즉 pi는 접미사도 되고 접두사도 되는 최대 길이이기에 최소 길이를 구하여야 한다는 것을 알 수 있다.

ababa의 pi[S-1]은 3이다. S[:3], S[2:]이 모두 aba로 같기 때문이라는 것을 알 수 있다.

이 때 aba의 pi값은 1이 되는데,

S[:3]에서 S[0]과 S[2]이 같다는 의미이고 S[2:]에서 S[2]과 S[4]가 같다는, 즉 S[0]와 S[4]가 같다는 의미가 된다.

다시 말해서 pi[pi[S-1]-1]의 값이 양수일 경우 더 작은 값으로 문자열 S의 접미사도 되고 접두사도 되는 길이가 된다는 것이고

이는 반복적 동적 계획법을 사용하여 이전 항들의 최소 pi를 저장해 나간다면 

현재 pi[i]가 양수일 때 dp[pi[i]-1]도 양수라면 dp[i] = dp[pi[i]-1], 아니라면 dp[i] = pi[i] 라는 점화식을 이용하여

O(N)만에 계산하여 구할 수 있다. 이후 0보다 큰 pi값들에 대하여 S-pi[S-1]값을 더해주면 풀 수 있는 문제이다.