[Algorithm] 보이어 무어 알고리즘

보이어-무어 알고리즘

- 오른쪽에서 왼쪽으로 비교, 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘입니다.
- 패턴에 오른쪽 끝에 있는 문자가 불일치하고, 이 문자가 패턴 내에 존재하지 않는 경우, 이동거리는 패턴의 길이 만큼이 됩니다.

- M은 전체 문자열이고 N이 찾으려는 문자열이라고 할 때.시간 복잡도는 일반적으로 O(n) 이하이고 최악의 경우에는 O(MN)가 됩니다.

"""
코드 출처 : https://mungto.tistory.com/124
"""


#문자열 검색하는 보이어 무어 알고리즘
def boyer_moore(pattern, text):
    #길이를 자주쓰므로 길이를 받아둔다.
    M = len(pattern)
    N = len(text)
    i = 0
    #반복은 최대 긴텍스트 길이 - 작은텍스트 길이
    while i <= N-M:
        #보이어 무어 알고리즘은 뒤에서부터 접근하므로 pattern길이의 -1을 해준다.
        #-1을 해주는 이유는 인덱스가 0부터 시작하기 때문이다.
        j = M - 1
        #뒤에서부터 검사하고 인덱스를 감소하는 형식이므로 0보다 이상일때만 동작한다.
        while j >= 0:
            #끝글자부터 비교하면서 같다면 하나씩 감소하면서 비교한다.
            if pattern[j] != text[i+j]:
                #글자가 틀리다면 제일마지막 글자 기준으로 find 함수를 호출한다.
               move = find(pattern, text[i + M - 1])
                break
            j = j - 1
        #인덱스가 -1이라는 뜻은 모든 글자가 맞았다는 이야기이다.
        if j == -1:
            #찾았으므로 true를 리턴한다.
            return True
            #인덱스 위치를 찾는다면
            #return i
        else:
            #-1이 아니라면 글자를 못찾은 것이므로 find에서 넘겨준 값만큼 옆으로 이동한다.
            i += move
    #여기까지 왔다면 끝까지 찾지 못한것이므로 False를 리턴한다.
    return False
    #인데스 위치로 한다면
    #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)

"""
코드 출처 : https://br-brg.tistory.com/37
"""

text = 'a pattern matching algorithm'
pattern = 'rithm'
s = pattern[::-1]
skip = list(range((len(pattern))))
 
i = len(pattern)-1
result = 0
 
while i < len(text):
    nxt = len(s)
    j = 0
    if s[j] == text[i]:
        while j < len(s):
            if s[j] != text[i-j]:
                break
            j += 1
        if j == len(s):
            result = 1
    else:
        while j < len(s):
            if s[j] == text[i]:
                nxt = min(j, nxt)
                break
            j += 1
    if result:
        break
    i += nxt
 
print(result)

 

참고 블로그 :

https://mungto.tistory.com/124

보이어-무어 알고리즘(문자열 검색, Python)

https://br-brg.tistory.com/37

[Python]보이어무어 알고리즘