专注于互联网--专注于架构

字符串查找算法:字符串查找算法BM算法

字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法则往往比KMP算法快上3－5倍。 但是，最坏的情况下，BM的时间复杂度貌似也是n×n。 具体就不说了，BM算法是通过往后跳动主文本字符串来实现快速非回溯查找的，跳动的算法就是用程序中的这句来实现的，下面： i = i + m - min(j, 1+last(p, T[i]) ); 而last是一个求文本字符串中的 [阅读全文] [PDF]