문자열 검색 알고리즘
핵심 아이디어
2가지 규칙을 이용해 불필요한 비교를 건너뛰는 방식
1. Bad Character Rule(나쁜 문자 규칙)
•
패턴을 오른쪽에서 왼쪽으로 비교
◦
불일치 발생 → 해당 불일치 문자가 패턴 내 어디에 있는지 확인하고 해당 위치까지 점프
만약 패턴에 해당 문자가 없다면, 패턴 길이만큼 점프
2. Good Suffix Rule(좋은 접미사 규칙)
•
불일치가 발생했지만, 패턴의 오른쪽 일부가 이미 일치한 경우 → 일치한 부분(접미사)을 최대한 유지하면서 점프
일반적으로 보이어-무어 알고리즘은 두 규칙을 모두 사용하지만, 구현 시에는 Bad Character Rule만 구현해도 기본적인 동작이 가능!
시간 복잡도
•
최선 : O(N/M)
◦
거의 패턴 길이만큼 점프
•
평균 : O(N)
•
최악 : O(NM)
◦
EX : 모든 문자가 동일할 때
코드와 함께 살펴볼까요?
# bad character rule만 구현한 버전
def boyer_moore(text, pattern):
n = len(text)
m = len(pattern)
# 1. Bad character table 생성
bad_character = {}
for i in range(m):
bad_character[patter[i]] = i # <문자, 마지막 인덱스>
# 2. 검색 시작
shift = 0
results = []
while shift <= n - m:
j = m - 1
# 오른쪽에서 왼쪽으로 비교
while j >= 0 and pattern[j] == text[shift + j]:
j -= 1
if j > 0:
# 패턴이 완전히 일치하는 경우
results.append(shift)
# 패턴의 마지막 문자가 텍스트에 없으면 m만큼 점프
shift += (m - bad_character.get(text[shift + m], -1)) if shift + m < n else 1
else:
# 불일치 : bad character rule로 점프
shift += max(1, j - bad_character.get(text[shift + j], -1))
# 실행
text = "ABAAABCD"
pattern = "ABC"
matches = boyer_moore(text, pattern)
print("패턴 발견 위치: ", matches)
Python
복사
참고 자료
