보이어 무어 알고리즘은 String 검색 기법 중 하나인 알고리즘이다.
컨셉 자체는 패턴 불일치의 대부분은 후반부에 발생하기 때문에 String 배열의 뒤에서 부터 검색하는것이다.
각 배열에 대한 skip 표를 만들어 두고 뒤에서 부터 검색해서 불일치가 발생할 경우 어디로 Skip해야할지 판단하는 식이다.
예를들어 ESNTEST 라는 단어에서 TEST를 검색해보자
T(3) E(2) S(1) T(0) 다른 문자 (4)- 괄호안의 숫자는 Skip 범위
1차
ESNTEST
TEST
-> T가 같음 , S가 같지 않음. 비교 했던 N의 경우 Skip표에 존재하지 않기 때문에 4만큼 이동
2차
ESNTEST
TEST
-> 일치.
설명이 좀 부족하지만 Skip 표를 만들어 Skip한다는 점에서 다른 패턴 매칭 알고리즘 보다 시간 복잡도가 낮다는게 중요.
접두어에 관한 더 복잡한 알고리즘이 있으므로 아래 링크 참조