보이어-무어법

일반적으로 파이썬에서 문자열 검색을 하려면 표준 라이브러리(in, not in)를 사용하는 것을 추천하지만, 사용하지 않는다면 브루트 포스법이나 보이어-무어법을 사용하는 경우가 많습니다. 

 

보이어-무어법

 

KMP법보다 효율적이어서 실제 문자열 검색에서 널리 사용됩니다. 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행합니다. 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정합니다.

 

① ABCXDEZCABACABAC에서 ABAC를 검색하는 과정

② 텍스트와 패턴의 첫 문자를 위아래로 나란히 놓고 패턴의 마지막 문자 C에 집중합니다. X는 패턴 안에 포함되어 있지 않습니다. 패턴을 오른쪽으로 한칸씩 이동해도 말이죠. 

 

③ 한번에 오른쪽으로 4칸을 밀어서 다음과 같은 상태를 만듭니다. 즉, 패턴에 포함되지 않은 문자를 텍스트에서 발견하면, 과감히 건너뜁니다.

 

④ 여기서 패턴의 마지막 문자 C를 텍스트와 비교하면 일치하므로, 1칸 앞의 문자 A로 되돌아가서 다음과 같은 상태로 만듭니다. 여기서도 1칸, 2칸을 밀어도 텍스트의 Z와 일치하지 않으니, 다시 한번에 오른쪽으로 3칸을 밀어버립니다.

 

⑤ 여기서 한번만 오른쪽으로 밀면 패턴의 A와 텍스트의 A가 일치합니다. 패턴에 포함되는 문자가 있다는 말이죠. 그러므로 오른쪽으로 1칸만 이동하겠습니다.

 

⑥ 이 상태에서 맨 끝부터 차례로 비교하면 모든 문자가 일치하므로 검색에 성공합니다.

 

그런데 보이어-무어법도 각각의 문자를 만났을 때 패턴을 이동할 크기를 저장하는 표를 미리 만들어 놓을 필요가 있습니다. 패턴 길이가 n일 때 이동할 크기는 다음과 같이 결정합니다.

 

패턴에 포함되지 않는 문자를 만났을때

- 패턴 이동량: n, 과정 ②와 같습니다.

 

패턴에 포함되는 문자를 만난 경우

- 마지막에 나오는 위치의 인덱스가 k이면 이동량은 n - k - 1입니다. 과정 ⑤와 같습니다.

- 같은 문자가 패턴 안에 중복해서 존재하지 않으면 패턴의 맨 끝 문자의 이동량은 n입니다. 

 

최종 코드입니다.

def bm_match(txt: str, pat: str) -> int:
    skip = [None] * 256

    # 건너뛰기 표 만들기
    for pt in range(256):
        skip[pt] = len(pat)
    for pt in range(len(pat)):
        skip[ord(pat[pt])] = len(pat) - pt - 1

    # 검색하기
    while pt < len(txt):
        pp = len(pat) - 1
        while txt[pt] == pat[pp]:
            if pp == 0:
                return pt
            pt -= 1
            pp -= 1
        pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat) - pp else len(pat) - pp

    return -1