http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140KMP 알고리즘은 O(m+ n)<m은 pattern 의 길이, n 은 text의 길이> 의 Optimal Time 을 가진다.
BM(Boyer-Moore) 알고리즘은, KMP 알고리즘이 left-to-right 비교 알고리즘인데 비하여 right-to-left 비교 알고리즘이다. 일단 Patern과 Text의 일부분을 right-to-left 로 비교해 나간 후 mismatch가 일어나면 mistmatch된 Text의 문자를 가져와서 LOF(Last-Occurrence Function) 로 부터 오른쪽으로 점프할 Index의 값을 얻는다.
BM 은 무한루프에 빠질 가능성이 존재하는데, bad character(mismatch 된 Text의 문자) 의 LOF 값이 현재의 Index 보다 클 경우 문제가 발생한다. 생각해 보면 이유를 쉽게 알 수 있는데 비교 Index가 앞 뒤로 이동을 반복하게 된다.
BM 알고리즘은 O(mn + s)<s는 LOF 를 만드는 시간> 시간에 수행되는 알고리즘이고 DNA 와 같이 한정된 문자로 반복되는 Text 에서 최악의 성능을 발휘한다. 그러나 English Text 와 같은 자유문법의 문자열일 경우 상당히 빠른 수행시간을 보여준다. 이 경우 Brute-force 알고리즘과 비교하면 매우 뛰어난 수행시간을 보인다.
