lPS1 KMP 알고리즘 (Knuth-Morris-Pratt Algorithm) KMP 알고리즘(Knuth-Morris-Pratt Algorithm)KMP 알고리즘을 만든 Knuth, Morris, Pratt의 이름 앞 글자를 따서 명명한 알고리즘이다. 우리가 찾고 싶어하는 길이 N의 문자열을 Pattern String으로, Pattern String을 찾을 길이 M의 문자열을 Text String으로 하자. 단순한 Brute Force 문자열 탐색 알고리즘의 시간 복잡도는 O(N*M)인 반면에, KMP 알고리즘의 시간 복잡도는 O(N+M)이다. 1. Brute Force와의 비교Text String을 "AABABCAABACABC"로, Pattern String을 "ABACABC"라고 할 때 Brute Force로 진행하면 다음과 같은 과정으로 문자열을 탐색한다. Brute For.. 2024. 5. 5. 이전 1 다음