[강한구] Shift or

비트로 and, or연산을 통해 문자열 매칭을 하는 알고리즘 이다.

예제를 통해 흐름을 파악해보자

원본 : GCATCGAGAGACGTACG

패턴 : GAGAGACG

 우선 비트 마스크를 만든다. (비트마스크는 충분한 길이의 unsigned int형 배열로 선언)
패턴에 해당하지 않는것은 모두 1로 초기화해준다.

나중에 원본텍스트와 or연산시 패턴길이를 정해 주기위해서 lim이 비트마스크 만드는단계에서 필요하다.
패턴이 다섯글자면 하위 4비트를 0, 나머지를 1로 해준다.
예로든 패턴의 lim은 1111111~11110000000

동그라미를 보니 뭔가 감이 잡힌다. . .
우선, 가장 오른쪽 G부터 시작해서 가장 왼쪽 G까지 비트 0이 도달하게 되면 문자가 매칭되었다고 할수있다.

지금까지 매칭을 시작하기 위한 준비단계를 했다,
비트마스크, 패턴의 길이를 나타내는 lim

이젠 실제로 문자열 매칭하는부분을 살펴보기로 하자.

비트의 상태는 아래 그림과 같다. 모든 비트는 32비트이며, 표현이 안된 부분은 모두 1이다.

state값이 lim값보다 작다는것은, 끝까지 문자열 매칭을 했다는 것이다.
참조 : http://www-igm.univ-mlv.fr/~lecroq/string/node6.html