노션 정리본 : https://mint-truck-226.notion.site/439124467c2143ff8f6aff46d72a6cc3
1. 개념
“불필요한 건 건너뛰면서 검색을 빠르게!”
보이어 무어란, 문자열 검색에 사용되는 알고리즘 (문자열에서 특정 패턴 찾기)
근데, 브루트 포스 & KMP보다 훨씬 더 빠르다!
시간복잡도 : 최악 - O(N) / 평균 - O(N/M)
KMP와 차이점
- skip 배열을 만들고, 문자열과 패턴을 비교한다는 건 동일하지만
- 차이점은 다음과 같다.
1) skip 배열 만드는 방식 (KMP는 접두사 접미사 비교, 보이어무어는 패턴 value 구하는 공식)
2) 문자열 비교 방향 (KMP는 왼쪽 오른쪽, 보이어무어는 오른쪽 왼쪽)
2. 원리
“뒷 부분에서 불일치가 일어날 확률이 높다!”
1) 오른쪽 끝부터 비교한다.
2) 본문의 문자열과 패턴에서 불일치 하는 문자를 찾는다.
3) 일정 길이만큼 이동하여 비교를 계속한다.
방법 1. Bad Character Method (혹은 Bad match table)
bm.py 코드를 실행할 때,
s1 = "EAABCBABC"
s2 = "CBABC"
가 입력으로 주어지면
skip 배열의 값이 최종적으로 어떻게 되는지와 코드에서
pt += skip[ord(txt[pt]) - ord('A')] 가 호출되기 직전에 s1과 s2의 어떤 부분을 비교하고 있는지를 표시하세요(여러 개가 있다면 모두). 이 코드는 책에 있는 코드에서 저번에 말씀드린 부분을 수정하고 입력으로 영문 대문자만 들어오는 상황을 가정했습니다.1) skip 테이블을 만든다.
2) 오른쪽에서 왼쪽으로 이동하면서 패턴과 문자열을 비교한다.
def bm_match(txt: str, pat: str) -> int:
# 1) skip 테이블을 만든다.
skip = [None] * 26 # 메모리 낭비 방지 + 알파벳 26개(대문자만)
for pt in range(26):
skip[pt] = len(pat)
for pt in range(len(pat) - 1):
skip[ord(pat[pt]) - ord('A')] = len(pat) - pt - 1
# 2) 오른쪽에서 왼쪽으로 이동하면서 패턴과 문자열을 비교한다.
pt = len(pat) - 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]) - ord('A')] if skip[ord(txt[pt]) - ord('A')] > len(pat) - pp else len(pat) - pp
return -1
if __name__ == '__main__':
s1 = input('텍스트를 입력하세요:')
s2 = input('패턴을 입력하세요:')
idx = bm_match(s1, s2)
if idx == -1:
print('텍스트 안에 패턴이 존재하지 않습니다.')
else:
print(f'{idx + 1}번째 문자가 일치합니다.')
#s1 : EAABCBABC
#s2 : CBABC
앞선 방법 1에 대해, 이동이 불가능한 경우(문자열에서 찾은 불일치 문자 ‘A’ 위치보다 패턴의 ‘A’ 위치가 뒤 쪽인 경우에는) Good Suffix Shift 방법을 사용한다!
방법 2. Good Suffix Shift
1) 패턴의 오른쪽 부분과 일치하는 접미부(good suffix)를 찾는다.
→ 오른쪽부터 왼쪽으로 일치여부를 조사하되, 불일치 문자를 만나면 멈춘다.
2) 패턴에서 good suffix와 일치하는 문장을 이동시키고, 일치 여부를 확인한다.
❓ 이해가 도무지 안 되었던 부분
2) 패턴과 문자열을 비교하는 부분에서, 사진을 보면 패턴의 이동이 즉, 패턴[0] C가 문자열 A 다음 위치로 이동해야 하는 거 아닌가? 싶었는데 코드는 C가 A의 위치로 이동하게끔 했다.
진짜 하루를 붙잡았는데, 그 이유를 모르겠다. 그래서 GPT한테 물어봤으나..
이렇게 답을 주었지만, 아직도 왜 그런지는 잘 모르겠다.
그냥 "코드는 그렇게 하고 싶다"로 봐야 할까..?
