반응형
KMP
-
KMP(Knuth-Morris-Pratt)algorithm 2020. 2. 26. 17:10
KMP(Knuth-Morris-Pratt)는 문자열 검색하는 알고리즘으로 시간 복잡도가 O(N+K)로 짧은 시간안에 문자열을 찾을 수 있는 알고리즘이다. 여기서 N은 대상 문자열 K는 찾고자하는 문자열이라 하자. 문자 하나씩 비교를 하며 문자열 2개를 비교하여 검색할 경우 O(NM)의 복잡도로 검색을 하게 된다. KMP는 문자열을 비교할때의 정보를 다음 문자열끼리의 비교에 이용을하여 시간복잡도를 개선하는 방법이다. KMP를 이해하기 위해서는 접미사(prefix)와 접두사(surffix)를 알아야한다. 이를 이용하여 pattern 대상의 문자열을 가지고 PI배열을 만들어야 하는데, PI배열은 아래와 같은 정보를 가지고 있다. ex) pattern = "ABCABC" i 부분문자열 pi[i] 0 A 0 1 ..
반응형