대엉코딩

1.개요

- 보이어모어 알고리즘 역시 kmp 알고리즘과 마찬가지로 패턴과 텍스트 중 패턴을 preprocessing 하는 방식이다.

- kmp 알고리즘과는 반대로 패턴을 텍스트의 특정 위치에 놓고 비교를 할 때

  kmp는 패턴의 앞 쪽부터 차례대로 비교를 시작하는 반면 (왼쪽에서 오른쪽)

  보이어모어는 패턴의 뒤 쪽부터 차례대로 비교를 시작한다. (오른쪽에서 왼쪽)

2.아이디어

- 브루트포스 방식과 어떤차이점을 가지고 수행시간을 단축시켜주느냐~ 인데.

- 보이어모어 알고리즘에서는 두가지의 큰 아이디어가 있다.

    -> Looking-glass heuristic

        : 패턴의 뒤 쪽부터 비교를 시작한다.

    ->Character-jump heuristic

        : 패턴을 구성할 수 있는 모든 글자의 마지막 발생위치를 미리 구해서 테이블 형태로 저장해 놓는다.

          텍스트와 패턴을 뒤쪽에서부터 비교해 오다가 불일치 발생시 그 때 위치의 텍스트 문자가 패턴의 마지막에 등장한 문자의 위치를

          맞춰 패턴을 옮긴다.

이해하기 위한 간단한 이론적 예시는 아래와 같다.

3. 전처리(preprocessing)

- 2번에서 말씀드렸다싶이 전처리 과정은 매우간단하며 패턴을 한번 쓱 스캔하면 되므로 시간도 오래걸리지 않습니다.

- 앞에서부터 보면서 뒤쪽에 등장할 때 마다 그 위치로 문자열테이블을 업데이트 해주시면 되겠습니다.

- 처음에 테이블을 만들어 -1로 초기화 시키고 위의 작업을 수행하면 전처리후에도 여전히 -1값을 가지는 문자는 텍스 

  트에는 있을 수 있으나 패턴에는 존재하지 않는 문자이므로 이 경우 패턴의 길이만큼 jump를 해주시면 되겠습니다.

4.The BoyerMoore Algorithm

-주의 해야할 점 하나는

  mismatch가 발생한 위치에 있는 문자가 현재 패턴의 문자열 위치보다 뒤쪽에 있을경우

  그대로 옮겼다가는 패턴이 다시 앞쪽으로 갈 수 있고 무한반복과 중복 처리 등이 발생할 수 있다.

  이 경우는 그냥 한칸 뒤로만 옮겨주는 것으로 대체한다.

5. 분석(Analysis)

- 시간 복잡도 : O(n*m+s)

- 최악의 경우를 분석해보면 심지어 브루트포스방식의 시간복잡도인 O(n*m)보다도 s만큼의 시간이 더 걸린다.

- 최악의 경우 예시를 보자면

        TEXT= aaaaaaaaaa........a

        PATTERN = baaa

-최악의 경우는 문자의 범위가 좁은 DNA Sequence나 이진문자열 같은 곳에서는 발생할 확룰이 꽤 있다.

- 하지만 영어 알파벳이나 한국어 처럼 문자의 범위가 매우 큰 경우 매우 효율적으로 빠르게 동작한다.