KMP1 [Algorithm] KMP 알고리즘 (Knuth-Morris-Pratt Algorithm) 문자열 검색 문자열 검색 문제는 문자열 H가 주어졌을 때 문자열 N을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제다. 이 문제를 풀 수 있는 가장 간단한 방법은 H의 가능한 모든 위치에서 다 시도해보는 방법이다. H의 각 위치의 부분 문자열이 N과 일치하는지 일일히 다 확인하는 것이다. 시작 위치의 수는 O(∣H∣)가 되고, 각각 비교에 걸리는 시간은 O(∣N∣)이 걸리기 때문에, 총 걸리는 시간은 O(∣H∣∣N∣)이다. C의 strstr(), C++의 string::find(), 자바의 indexOf(), 자바스크립트의 String.prototype.indexOf() 등 대부분 표준 라이브러리에서 사용된다. KMP(Knuth-Morris-Pratt).. 2023. 3. 23. 이전 1 다음