模式匹配算法的研究与应用论文

本文主要讲述了串的模式匹配算法，包括BF算法、RK算法、KMP算法、BM算法，使用不同的算法实现目标串查找子串，重点在于分析的过程，通过不同的算法分析提高逻辑思维能力

模式匹配的目的就是在目标串中查找与模式串相等的子串。在这里称呼主串为s，模式串为t，主串的长度为n，模式串的长度为m

暴力算法，将目标串和模式串的每个字符都进行一一比较。性能最差，但是使用最广，因为实现简单，而且在字符串较小的情况下耗费的性能也很小。

O(n*m)

RK算法把字符串比较问题，转换为了Hash值比较问题。 将模式串t的每个字符的比较改成了将串作为整体与目标串进行哈希值比较，这样就减少了比较次数 以前模式串与子串的比较需要比较每个字符，现在只要整体比较依次哈希值就可以。所以减少了比较次数。

哈希算法

这里我们可以发现一个Hash冲突问题，比如"abc"和"bc"的Hash值是一样的，因为最高位是0。所以还需要进行哈希冲突算法。

哈希冲突算法：

利用前一个结果计算下一个哈希值 这是因为目标串的相邻子串，其实相差的只有第一个字符和最后一个字符，其他字符是相同的， 所以我们可以利用前一个计算结果减去前一个字符串的第一个字符串，加上这个字符串的最后一个字符就够了。

针对BF的弊端，在KMP算法中可以进行多字符的跳跃对比，以此来避免目标串的不必要回溯。

例子：

简单说明一下：

真子串：

匹配：

例如：目标串："abxabcabcaby"，模式串："abcaby"

模式串的最大真子串为ab, 我们在匹配时，发现目标串的子串abcabc与模式串的前字符都匹配，最后一个字符不匹配 所以就从目标串的abcabc的后面abc开始与模式串进行匹配，而不需要匹配前面的abc了。

也就是从上一个a字符直接跳跃到了下一个a字符，而不是从b字符开始。

会存在一种情况：

实现思想：

它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP算法的三四倍。BM算法的原理很多复杂，比较难懂，学起来比较烧脑。 实现思想和KMP算法基本上是一样的，都是先计算模式串的真子串，之后再查找真子串的大小，当出现不匹配时，直接在真子串后进行匹配，区别于KMP算法，它是从后往前匹配的

这里比上面的KMP算法增加了一个坏字符规则，可以更快的跳跃，当然KMP算法本身也可以使用坏字符规则

坏字符规则

好后缀规则