KMP1 [KMP] 문자열 알고리즘 KMP algorithm KMP (Knuth-Morris-Pratt) 알고리즘 문자열 검색, 짚더미(Haystack, H 문자열)에서 바늘(Needle, N 문자열)을 찾아봅시다! 불일치가 일어났을 때 지금까지 일치한 글자 수를 이용해 다음으로 시도해야 할 시작 위치를 빠르게 찾아냅니다. 필요한 것: 부분 일치 테이블(partial match table) p[i] 를 만듭니다. pi[i]는 문자열 N[...i] (문자열 처음부터 i번째 까지 문자열)의 접두사도 되고 접미사도 되는 문자열의 최대 길이입니다. 예를들면 "aabaaba"에서 aaba는 접두사도 되고 접미사도 되는 최대 길이 문자열이므로, pi[6] = 4 입니다. KMP 알고리즘의 전체 반복문 수행 횟수는 O(|H|) 입니다. #include.. 2019. 8. 30. 728x90 이전 1 다음
