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

０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５
A B C X D E Z C A B A C A B A C
A B A C 일치합니다!

[그림 8-14] 패턴의 마지막 문자가 일치하는 경우

０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５
A B C X D E Z C A B A C A B A C
a A B A C 일치하지 않습니다!
b A B A C 패턴을 1칸 옮겨도 문자가 서로 다릅니다.
c A B A C 패턴을 2칸 옮겨도 문자가 서로 다릅니다.

[그림 8-15] 패턴과 텍스트의 문자가 다른 경우

패턴의 문자 'A'는 텍스트의 'Z'와 다르기도 하지만 텍스트의 ‘Z’는 패턴에 없는 문자입니다.

따라서 b , c 처럼 패턴을 1 ~ 2칸 옮긴다고 하더라도 패턴과 일치하지 않는 것을 알 수 있습
니다. 패턴을 한꺼번에 3칸 옮겨 그림 8-16의 상태로 만듭니다.

이렇게 패턴의 길이를 n이라고 하면 현재 검사하고 있는 텍스트의 문자 위치로부터 ‘다음에

검사할 패턴의 마지막 문자 위치’가 n만큼 떨어질 수 있도록 패턴을 옮기면 됩니다. 예를 들어
그림 8-13에서는 패턴을 4칸 옮겼지만 이번에는 검사하고 있는 텍스트의 위치(6)로부터 4만
큼 떨어진 위치(10)에서 검사를 시작하기 위해 패턴을 3칸 옮깁니다.

０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５
A B C X D E Z C A B A C A B A C
a A B A C 일치하지 않습니다!
b A B A C 패턴을 1칸 옮기면 일치하는 문자 ‘A’가 나옵니다.
c A B A C 패턴을 2칸 옮겨도 문자가 서로 다릅니다.
d A B A C 패턴을 3칸 옮기면 안 됩니다.

[그림 8-16] 패턴과 텍스트의 문자가 다른 경우

이렇게 옮긴 다음에 다시 검사를 시작해도 텍스트의 'A'와 패턴의 마지막 문자 'C'를 비교합니
다( a ). 하지만 문자 'A'는 패턴의 1, 3번째 인덱스에 들어 있습니다. 이런 경우에는 b 와 같이

패턴의 뒤쪽에 위치한 'A'가 텍스트와 위, 아래로 겹치도록 패턴을 1칸만 옮깁니다. d 와 같은
방법으로 패턴의 첫 번째 문자인 'A'와 겹치도록 하기 위해 3칸을 옮기면 안 됩니다. 패턴을 1
칸만 옮기면 다음의 그림 8-17과 같은 상태가 됩니다. 이후 b 의 상태에서 다시 패턴의 마지

막 위치에서 순서대로 문자를 비교하면 모두 일치하기 때문에 검색 성공입니다.

330 C 알고리즘