引言
KMP它并不是效率最高的算法,实际采用并不多。各种文本编辑器的”查找”功能(Ctrl+F),大多采用Boyer-Moore算法。
Boyer-Moore算法不仅效率高,而且构思巧妙,容易理解。1977年,德克萨斯大学的Robert S
. Boyer
教授和J Strother Moore
教授发明了这种算法。
在用于查找子字符串的算法当中,BM(Boyer-Moore)算法是目前被认为最高效的字符串搜索算法。 一般情况下,比KMP算法快3-5倍。该算法常用于文本编辑器中的搜索匹配功能,比如大家所熟知的GNU grep
命令使用的就是该算法,这也是GNU grep
比BSD grep
快的一个重要原因。