(转载)Boyer-Moore(字符串匹配)

引言

KMP它并不是效率最高的算法,实际采用并不多。各种文本编辑器的”查找”功能(Ctrl+F),大多采用Boyer-Moore算法。

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

(转载)字符串匹配(KMP)

引言

简单匹配模式算法的效率不高,原因在于匹配过程中有回溯。
示例:从左到右一个个匹配,如果这个过程中有某个字符不匹配,就跳回去,将模式串向右移动一位。

我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动,如果不一致,如下图:

A和E不相等,那就把i指针移回第1位(假设下标从0开始),j移动到模式串的第0位,然后又重新开始这个步骤:

思想

S[i]!=P[j]达到失配点,主串S要回到原来的i+1的位置(回溯),模式串P要回到第一个字符的位置,然后继续比较。每次到达失配点时,串S和串P的指针i,j都要回溯,因此效率比较低。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×