[자료구조와 함께 배우는 알고리즘][정렬 알고리즘] - 문자열 검색(보이어 무어법)

1. 보이어 · 무어법이란?

보이어 · 무어법은 KMP 알고리즘보다 이론이나 실제 효율 면에서 뛰어난 알고리즘이다 . 

패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행한다. 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정한다.

이처럼 패턴의 마지막 문자를 텍스트와 비교하여 일치하면 맨 뒤에 문자에서 1칸씩 앞으로가며 문자를 비교해야 한다. 

 

2. 보이어 · 무어 알고리즘 구현 코드

def bm(txt,pat):
    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
    

s1 = input("텍스트를 입력하세요.: ")
s2 = input("패턴을 입력하세요.")

idx = bm(s1,s2)

if idx == -1:
    print("텍스트 안에 패턴이 존재하지 않습니다.")
else:
    print(f"{(idx+1)}번째 문자가 일치합니다.")

 

 

3. 문자열 검색 알고리즘의 시간 복잡도

	브루트 포스	KMP	보이어 · 무어
문자열 검색 알고리즘의 시간 복잡도	O(mn) - 일반적 경우 O(n) - 일부러 꾸며 낸 패턴이 아닌 경우	O(n) - 최악의 경우에도 이에 속하며 처리하기가 복잡하고 패턴 안에 반복이 없으면 효율성이 떨어지기 때문에 파일을 차례대로 읽어 들이며 검색하는 경우에 사용하면 좋다.	O(n) - 최악의 경우 O( n / m ) - 평균 배열을 만드는 데 복잡한 처리 과정이 필요해서 효율성이 덜어진다. 이때 배열을 1개를 만들어 사용하는 경우는 충분히 빠르지만 2개를 만들어 사용하는 경우엔 매우 효율성이 떨어진다.