数据结构-串的模式匹配

串的模式匹配就是子串定位 *** 作。给定两个串s="s0 s1 ... s(n-1)"和t="t0 t1 ... t(m-1)"（其中n和m分别是串s和t的长度），在主串s中寻找子串t的过程称为模式匹配，t称为模式。如果在s中找到等于t的子串，则称匹配成功，返回t在s中的首次出现的下标位置；否则匹配失败，返回-1。

本文介绍三个串模式匹配算法，分别是简单回溯算法（Brute-Force，BF算法）、KMP算法、KMP算法的改进。

从主串s的第0个字符开始，与模式串t的第0个字符开始逐字符比较，不相同时回溯到模式串t的第0个和主串s的第1个字符，重新开始比较。以此类推，直到t的所有字符完成匹配，则匹配成功，否则匹配失败。

BF算法速度慢的原因是存在大量不必要的回溯，即在某一趟与t的匹配过程失败后，需要返回s串开始字符的下一字符重新开始比较，这对于某些模式串t来说是不必要的。例如，若s=12123123132，t=12313，在t与12 12312 3132中加粗子序列进行比较时，在 2 处发生失配，BF算法接下来将t与121 23123 132、1212 31231 32、12123 12313 2比较。由于t中的231、312与其开始的123并不相同，显然t与121 23123 132、1212 31231 32的比较是不必要的。

KMP算法就是利用模式串中与模式串开头部分子串的重复性来减少重复回溯，实现新一轮比较的直接跳转。 具体来说，KMP算法利用一个数组记录模式串中每一个字符前面有几个字符与模式串从头重复，在与s串比较失配时，直接跳转到重复子串的下一个字符继续比较，而不用跳转至模式串t的第0个字符。

算法步骤： ①计算跳转数组next。②利用KMP算法进行模式匹配。

next数组通过递推计算，即如果当前字符 t[j] 的前一个字符 t[j-1] 与其 next[j-1] 指向的字符 t[next[j-1]] 相同，意味着 t[j] 前的 next[j-1]+1 个字符与从 t[0] 到 t[next[j-1]] 的子串相同，因此 next[j]=next[j-1]+1 ；如果不相同，则递推至 t[next[j-1]] 的next值指向的字符，与 t[j-1] 比较，直到确认 t[j] 前与 t 串从头重复的字符数，或者无重复字符标记为 0 。

注意此处的函数返回参数类型为int*，用于 返回一位数组 ，且返回的这个一位数组必须在函数中用static定义。

KMP算法进行模式匹配时，只需在回溯时将 j 指针赋值为 next[j] 。需要注意的是，若 next[j] 为 -1 ，则意味着 t[j] 前面没有与 t 从头重复的字符，且 t[j] 与 s[i] 失配，则 i 和 j 均加 1 。

考虑更特殊的模式串，还能进一步减少不必要的回溯次数。例如，s=111211112，t=11112，按照上述next的计算方式，next={-1,0,1,2,3}。当 i=3, j=3 时失配，此时 s[i]=2, t[j]=1 ，由于 next[j]=2 ，于是 j 跳转为 2 ，t=11 1 12与s=111 2 11112比较。由于 t[next[j]]=t[j] 也为 1 ，必然与 s[i]=2 不相同，显然这次回溯也不必要。

总结来说， 当失配的字符与待跳转的字符相同时，跳转一步并无意义，可再跳一步 ，即将当前字符置为跳转后字符的next值。

KMP算法也是比较著名的模式匹配算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 发表的一个模式匹配算法。可以大大避免重复遍历的情况。

如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母 "f" 和 "x" 不相等。如下图：

T = “abcdex”

j123456

模式串 abcdex

next[j] 011111

T = "abcabx"

j 123456

模式串T abcabx

next[j]011123

T = "ababaaaba"

j———————123456789

模式串T——— ababaaaba

next[j]————011234223

T = "aaaaaaaab"

j———————123456789

模式串T——— aaaaaaaab

next[j]————012345678

next数组其实就是求解字符串要回溯的位置

假设，主串S= “abcababca”模式串T=“abcdex”，由以上分析得出next数组为011111，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。

KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的数组就是012345；

当开始匹配时，当i= 5，j = 5时，我们发现字符"b"与字符“a”不相等，如上图，j = next[5] = 4

由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的后续字符的next[j],那么next数组为{0,0,0,0,0,5}

在求解nextVal数组的5种情况

本文主要讲述了串的模式匹配算法，包括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算法本身也可以使用坏字符规则

坏字符规则

好后缀规则

---