[알고리즘] Boyer-Moore 알고리즘

요즘 보고 있는 책이다. 전반적으로 C++ 코드도 깔끔하고 볼만한 책이다.

텍스트 패턴 매칭부분을 보면서 Boyer-Moore알고리즘을 보는데, 와~ 하고 감탄했다.
BM패턴을 보기전에 과연 어떻게 패턴을 찾는 알고리즘을 개선시킬까 잠깐 고민하고 봐서 그런지 더 와닿은거 같다.

BM알고리즘의 원리는 간단하다.
1. 비교하는 문자열을 뒤에서 부터 확인
2. 비교하는 문자열에 없는 문자가 오면(last(c) == -1), 문자열 개수만큼 건너뛰기

원리는 간단한데, 효과는 강력한 알고리즘.. 멋진 패턴 중 하나인거 같다.

Moore의 홈페이지
http://www.cs.utexas.edu/users/moore/

관련 ppt 자료

invalid-file