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

여기서 텍스트의 초록색 문자 "AB"와 패턴의 "AB"가 일치한다는 점을 이용하면 됩니다. 이 부

분은 ‘이미 검사를 마친 부분’이므로 텍스트의 'X' 다음 문자부터 패턴의 "CABD"가 일치하는
지만 검사하면 됩니다.

그래서 다음과 같이 "AB"와 'X'를 한 번에(3칸) 이동시키고 3번째 문자인 'C'부터 검사하면 됩

니다.

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

이와 같이 KMP법은 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구
합니다. 이런 방법으로 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높입니다.

하지만 몇 번째 문자부터 다시 검색을 시작할지 패턴을 이동시킬 때마다 다시 계산해야 한다
면 높은 효율을 기대할 수 없습니다. 그래서 ‘몇 번째 문자부터 다시 검색할지’에 대한 값을 미

리 ‘표’로 만들어 이 문제를 해결합니다.
다음 그림에서 왼쪽 그림은 텍스트와 패턴이 일치하지 않는 상태를 나타내고, 오른쪽 그림은 몇 번째 문자부터 검사를 다
시 시작할지를 나타내었습니다.

a 1번째 문자가 일치하지 않습니다.
X ? ? ? ? ? ? ? ? ? ? ? ? ? X ? ? ? ? ? ? ? ? ? ? ? ? ?
０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３
A B C A B D A B C A B D
× ●
1번째 문자부터 검사를 다시 시작합니다.
b 2번째 문자가 일치하지 않습니다.
A X ? ? ? ? ? ? ? ? ? ? ? ? A X ? ? ? ? ? ? ? ? ? ? ? ?
０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３
A B C A B D A B C A B D
● × ●
1번째 문자부터 검사를 다시 시작합니다.
c 3번째 문자가 일치하지 않습니다.
A B X ? ? ? ? ? ? ? ? ? ? ? A B X ? ? ? ? ? ? ? ? ? ? ?
０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３
A B C A B D A B C A B D
● ● × ●
1번째 문자부터 검사를 다시 시작합니다.
d 4번째 문자가 일치하지 않습니다.
A B C X ? ? ? ? ? ? ? ? ? ? A B C X ? ? ? ? ? ? ? ? ? ?
０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３
A B C A B D A B C A B D
● ● ● × ●
1번째 문자부터 검사를 다시 시작합니다.

08•문자열 검색 325