字符串匹配算法

引入概念主串和模式串

 

假设主串长度为n，模式串长度为m

 

BF算法(Brute Force)

就是遍历，时间复杂度O(n*m)

 

RK算法

哈希之后遍历，比数字比比字符串要快。

时间复杂度是O(n)。

比完数字之后再比一下字符串可以避免散列冲突。(极端情况下是O(n*m)，哈希值全部都一样)

 

BM算法

通过上面的算法，我们知道字符串匹配，其实就是模式串在主串上的滑动。

在这个想法的基础上，我们想要减少他的时间复杂度的方法就是跳过那些我们不需要匹配的字符串。

以下图为例

这个c和d并不匹配，在这种情况下，我们就可以直接移动3位。就是模式串的长度。

但其实这是一个特例，这个特例在于模式串中并没有c这个字符。

以下图为例，我们接着上图移动3位后

我们发现a和d不匹配，这个时候我们不能移动3位，因为a在模式串里面存在，所以只能移动2位。

 

我们把上述规则称为坏字符规则。

 

其实把上面的方法做扩展，我们可以得到好后缀规则。

 

好后缀规则就是我后面几个字符是有匹配到，但是没有全部匹配，但是这个匹配到的字符串在整个字符串中还有。

匹配到的字符串称为u，那么我们可以将模式串表示称x1 + u + x2 + u。

在这种情况下，第一个u应该和主串进行匹配。

以下图为例，

那除了这种情况还有什么问题吗？

以下图为例，

从图上可以看出，另外一种情况就是，这个匹配的字符串u的部分匹配。

u = bc

模式串中只有一个u，这个时候得对u做分析，如果匹配到了前缀字符串，则按需移动。

 

总结一下:BM的算法目的就是尽可能的减少全部遍历，然后考虑所有的corner case(各种枚举)，总体可以归结为2个规则，坏字符规则和好后缀规则。两个方法取最大的移动位数进行移动。坏字符规则的实现比较耗内存，为了节省内存。我们一般使用好后缀方法来实现BM算法。

 

根据统计BM算法是字符串匹配算法中最高效、最常用的字符串匹配算法。

 

KMP算法

KMP算法的核心思想，就是先验知识。我们假设主串是a，模式串是b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。

 

理解KMP算法的核心在于，模式串已匹配部分的前缀子串的后缀子串等于移动后的模式串的前缀子串。

 

根据这个结论我们可以提前生成一个next数组。

 

根据next数组我们可以得到如下图所示。

 

KMP算法的主串指针是每次移动加1的

 

总结

BM算法是贪心算法，KMP算法是稳定算法。数据量大的时候BM算法比KMP算法好3到5倍，小数据量情况下差不多。

 

KMP算法时间复杂度O(m+n)

 

利用坏字符规则，BM算法在最好情况下的时间复杂度O(n/m)。