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[..
14959번: Slot Machines - KMP N개의 수들이 주어질 때, 이 수열은 처음 K개의 원소를 제외하고 주기 P를 갖는다.이 때, K+P가 최소가 되는, 같다면 P가 최소가 되는 K와 P를 출력하는 문제이다. 주기를 찾는 문제는 KMP에서 광고문제로 설명한 적이 있다.문자열을 이루고 있는 최소의 주기를 구하는 방법은 문자열의 길이가 S일 때, S - pi[S-1]이다.이를 이용하려면 먼저 pi배열을 구하여야 한다.pi[i] = N[...i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이로주기가 시작되는 부분을 알 수 없으므로 모든 N에 대하여 확인해봐야하므로 시간복잡도가 O(N^2)이다.그러나 여기서 N개의 수를 뒤집어서 생각한다면 주기의 시작부분은 처음부터가 되게 되며단 한번의 pi배열..
KMP
KMP(Knuth Morris Pratt)는 문자열 검색 알고리즘입니다.길이가 H인 문자열에서 길이가 N인 문자열을 검색하고 싶을 경우완전탐색으로 보게 된다면 시간복잡도가 O(HN)이 되지만KMP는 O(H + N)만에 문자열을 검색하게 해주는 알고리즘입니다.기본적인 원리는 문자열을 검색하다가 일치하지 않는 부분이 나왔을 경우H의 다음 글자와 N의 처음부터 비교하는 것이 아닌지금까지 일치했던 부분의 접미사도 되고 접두사도 되는 문자열의 최대 길이만큼은 또 다시 일치하므로그 길이 이후부터 비교해 나가는 방식입니다.이 때, 접미사도 되고 접두사도 되는 문자열의 최대 길이를 저장해놓은 테이블을부분 일치 테이블이라고 부르는데 이를 구하는 방법 또한N에서 자신을 제외하고 N을 찾는 방법으로 구할 수 있기에비슷한 두..