hellogaon

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[..