Page 324 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

08-3 KMP법

KMP법은 다른 문자를 만나면 패턴을 1칸씩 옮긴 다음 다시 패턴의 처음부터 검사하는 브루
트-포스법과는 다르게 중간 검사 결과를 효율적으로 사용하는 알고리즘입니다.

KMP법
브루트-포스법은 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고 다음 텍

스트의 위치로 1칸 이동한 다음 다시 패턴의 첫 번째 문자부터 검사합니다. 예를 들어 "apple"
이라는 텍스트에서 "app"이라는 패턴을 찾을 경우, 텍스트에서 패턴의 'a'를 찾은 다음에 텍
스트의 'p'를 찾으려면 다시 패턴의 'a'부터 검사합니다. 이렇게 하면 처음에 찾았던 패턴의 'a'
부터 다시 검사하기 때문에 비효율적입니다. 하지만 KMP법은 검사했던 위치 결과를 버리지

않고 이를 효율적으로 활용하는 알고리즘입니다.
D. E. Knuth, V. R. Pratt, J. H. Morris가 거의 같은 시기에 고안했기 때문에 이들의 이름 앞 글자를 각각 따서 KMP법
이라고 부릅니다.

그러면 텍스트 "ZABCABXACCADEF"에서 패턴 "ABCABD"를 검색하는 경우를 예로 들어
KMP 알고리즘에 대해 알아보겠습니다. 먼저 다음 그림과 같이 텍스트, 패턴의 첫 문자부터

순서대로 검사합니다. 텍스트의 1번째 문자 'Z'는 패턴에 없는 문자이므로 일치하지 않는다
고 판단합니다.

×
Z A B C A B X A C C A D E F
A B C A B D
×

그런 다음 패턴을 1칸 뒤로 이동시킵니다. 이때 패턴을 처음부터 순서대로 검사하면 패턴의

마지막 문자는 'D'여서 텍스트의 X와 일치하지 않습니다.

● ● ● ● ● ×
Z A B C A B X A C C A D E F
A B C A B D
● ● ● ● ● ×

324 C 알고리즘