[알고리즘 종류] 보이어-무어 알고리즘

- 보이어-무어 알고리즘

• 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘
• 패턴에 오른쪽 끝 문자부터 검사하고 불일치하면 패턴에서 일차는 문자를 찾아서 이동함.
• 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우 , 이동거리는 무려 패턴의 길이 만큼이 된다.

출처: https://devwooks.tistory.com/12

 

def boyer_moore(pattern, text):
    M = len(pattern)
    N = len(text)
    i = 0
    #반복은 최대 긴텍스트 길이 - 작은텍스트 길이
    while i <= N-M:
        j = M - 1
        
        while j >= 0:
            if pattern[j] != text[i+j]:
               move = find(pattern, text[i + M - 1]) # 제일 마지막 문자부터 찾기
               break
            j = j - 1

        if j == -1: # 인덱스가 -1이라는 뜻은 모든 글자가 맞았다는 뜻
            return i # 검색 성공
        else: #- 1이 아니라면 글자를 못찾은 것이므로 find에서 넘겨준 값만큼 옆으로 이동한다.
            i += move
    return -1 # 검색 실패
 
 
#불필요한 비교를 건너뛰기 위한 함수
def find(pattern, char):
    for i in range(len(pattern)-2, -1, -1):
        #마지막글자와 패턴중 일치하는 숫자가 있다면 그만큼 이동한다.
        if pattern[i] == char:
            return len(pattern) -i -1
    #일치하는 글자가 없다면 패턴의 길이만큼 이동한다.
    return len(pattern)