[5.29] 07-3 보이어, 무어법 Boyer-Moor method

보이어 무어법 알아보기

-> 가장 효율적인 문자열 알고리즘이다. 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행함

 

#보이어 무어법으로 문자열 검색하기

def bm_match(txt:str, pat:str) -> int:
  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

if __name__=='__main__':
  s1 = input('텍스트를 입력하세요 : ')
  s2 = input('패턴을 입력하세요 : ')

  idx = bm_match(s1, s2)

  if idx == -1:
    print('패턴없음')
  else:
    print(f'{(idx+1)}번째 문자가 일치합니다')

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

브루트 포스법 : O(n)

KMP법 : O(n) 이하

보이어 무어법 : O(n) 이하, 평균 O(n / m)

참고 - 문자 코드를 다루는 ord() 함수와 chr() 함수

ord() 함수 : 단일문자의 유니코드 unicode 포인트를 정수로 반환함

chr() 함수 : ord()의 역.