BF 和RK 算法

BF算法

BF算法，即暴风(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。

从字符串A虫查找B

首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则S向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。

该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。

模式串长度为m，主串长度为n，在主串，就会有n-m+1 个长度为m的子串，然后暴力对比n-m+1 个子串于模式串，找出对应配对的子串

RK 算法

在BF算法引进哈希算法

RK算法思想

假设我们有某个hash函数可以将字符串转换为一个整数，则hash结果不同的字符串肯定不同，但hash结果相同的字符串则很有可能相同（存在小概率不同的可能）。

算法每次从S中取长度为m的子串，将其hash结果与P的hash结果进行比较，若相等，则有可能匹配成功，若不相等，则继续从S中选新的子串进行比较。

假设要匹配的字符串的字符集值包含K个字符
，就可以用一个K进制来表示子串，这个K进制转化成十进制

比如包含a~z26个小写字母，映射到0 ~ 25个数字，a 表示 0，z 表示 25

相邻两个子串s [ i-1] 和 s[i] ( i 表示子串在主串的其实位置，子串的长度都为m），对应的哈希值计算公式有交集。使用s [i-1] 的哈希值 很快计算出s [i ]的哈希值

RF算法比BF 算法要高

模式串哈希值于每一个哈希值之间的比较时间复杂度是$O(1)$,总需要n-m+1给子串的哈希值，所以 时间复杂度是$O(n)$

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/90680468