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

e 5번째 문자가 일치하지 않습니다.
A B C A X ? ? ? ? ? ? ? ? ? A B C A X ? ? ? ? ? ? ? ? ?
０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３
A B C A B D A B C A B D
● ● ● ● × ◯ ●
2번째 문자부터 검사를 다시 시작합니다.
f 6번째 문자가 일치하지 않습니다.
A B C A B X ? ? ? ? ? ? ? ? A B C A B X ? ? ? ? ? ? ? ?
０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３
A B C A B DA B C A B D A B C A B DA B C A B D

● ● ● ● ● × ◯ ◯ ●
3번째 문자부터 검사를 다시 시작합니다.
[그림 8-12] 각 단계에서 검사를 다시 시작할 위치의 값

a ~ d … 패턴의 1 ~ 4번째 문자에서 검사에 실패한 경우에는 패턴을 옮긴 다음 1번째 문
자부터 다시 검사합니다.
e … 패턴의 5번째 문자에서 검사에 실패한 경우에는 패턴을 옮긴 다음 1번째 문자가

일치하므로 2번째 문자부터 다시 검사할 수 있습니다.
f … 패턴의 6번째 문자에서 검사에 실패한 경우에는 3번째 문자부터 다시 검사할 수 있
습니다.

표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아야 합니다. 이 과정에서
KMP법을 사용합니다. 패턴 안에서 중복되는 문자의 나열을 찾기 위해 패턴끼리 겹쳐놓고 생
각해 보겠습니다. 패턴의 1번째 문자가 서로 다른 경우 아래의 패턴을 1칸 뒤로 옮기고 1번째

문자부터 다시 검사합니다.

패턴 "ABCABD"를 1칸 뒤로 옮긴 다음 겹칩니다. 그림을 보면 초록색 부분이 겹치지 않으므로
패턴을 옮긴 다음 앞쪽의 1번째 문자부터 검사를 다시 시작해야 한다는 것을 알 수 있습니다.

따라서 표에서 2번째 문자(B)의 값을 0으로 합니다. 표에서 2번째 값이 0인 이유는 아래에 위
치시킨 패턴의 첫 번째 문자의 인덱스가 0이고 이 위치에서 다시 검사를 시작하기 때문입니다.

A B C A B D A B C A B D
A B C A B D — 0

패턴을 1칸 뒤로 옮깁니다. 문자가 일치하지 않으므로 표에서 3번째 문자(C)의 값을 0으로 합
니다.

A B C A B D A B C A B D
A B C A B D — 0 0

326 C 알고리즘