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 ¾Ë°í¸®Áò°ú ºñ±³ÇÏ¸é ¸Å¿ì ¶Ù¾î³ ¼öÇà½Ã°£À» º¸ÀδÙ.