「代码发布」实现KMP字符串匹配算法

字符串的前缀，后缀及部分匹配的值

a 前缀: {} 后缀: {} 最长相等前后最长度0
ab 前缀: {a} 后缀: {b} 最长相等前后最长度0
aba 前缀: {a}{ab} 后缀: {a}{ba} 最长相等前后最长度1
abab 前缀: {a}{ab}{aba} 后缀: {b}{ab}{bab} 最长相等前后最长度2
ababa 前缀: {a}{ab}{aba}{abab} 后缀: {a}{ba}{aba}{baba} 最长相等前后最长度3
ababa 的部分匹配值(PM)为 00123

而ababc 的部分匹配值(PM)为 00010

通过公式计算移动位数

子串移动位数 = 已匹配的字符串数 – 对应的部分匹配值

第一趟

主串 a b a b c a b c a c b a b
         ^
子串 a b c

已匹配的字符串数: 2
对应的部分匹配值: 0
位移 2-0 个位数

主串 a b a b c a b c a c b a b
         ^
子串     a b c

第二趟

主串 a b a b c a b c a c b a b
                 ^
子串     a b c a c

已匹配的字符串数: 4
对应的部分匹配值: 1
位移 4-1 个位数

主串 a b a b c a b c a c b a b
                 ^
子串           a b c a c

第三趟

主串 a b a b c a b c a c b a b
                       ^
子串           a b c a c

字串全部匹配完成

公式从何而来?

子串移动位数 = 已匹配的字符串数 – 对应的部分匹配值

主串 a b a b c a b c a c b a b
         |     | ^
子串     a b c a c
子串           a b c a c

位移子串移动位数 = 已匹配的字符串数 - 对应的部分匹配值对应的是图中的位移距离, 位移后只需从匹配失败的位置开始匹配

改进算法(next数组)

在上面的匹配中，每次匹配失败都需要去找上一个元素的部分匹配值，十分不方便，故将PM表整体右移一位（空缺用-1来补齐），就得到了 next 数组:

子串移动位数 = 已匹配的字符串数 – 对应的部分匹配值
Move = (j-1)-PM[j-1]
Move = (j-1)-next[j]

相当于将字串的比较指正回退Move位
j=j-Move=j-(j-1)+next[j]=1+next[j]

此时我们将next数组整体＋1方便计算

此时就十分方便了：
在字串第j个字符与主串发生失配的情况下，跳转到子串的next[j]位置重新与主串的当前位置进行匹配

如何进行计算next数组?
1按照上面的推导方法进行计算 (人工)
2使用下面的公式进行计算 (计算机)
$p_{1}p_{2}…p_{m}$ 为子串 $s_{1}s_{2}…s_{n}$ 为主串

$next[i]=\left\{\begin{array}{l}0 &j=1 \\ max\{k|1<k<j且’p_1…p_{k-1}’=’p_{j-k+1}…P_{j-1}’\} &当此集合不空时 \\1 &其他情况\end{array}\right.$

执行结果

C:\Users\enjoy\CLionProjects\untitled\cmake-build-debug\untitled.exe
11

KMP算法的进一步优化 (nextval)

next 数组在某些的情况下是存在缺陷的，例如下面的情况

'aaaab'与'aaabaaaaab'进行匹配时

当p[4]与s[4]失配的情况下按next数组我们还需要进行 s[4]与p[3], s[4]与p[2], s[4]与p[1]的3次匹配，实际上这些匹配是毫无意义，必然失配的，怎样导致这种情况发生的呢？首先第一次失配我们是使用 s[4]与p[3] 进行比较，然后我们使用 s[4]与p[next[3]]进行比较，若此时 p[next[3]]==p[3] 那我们岂不是用相同字符串重复比较了吗？毫无意义，下面我们尝试进行优化以处理此情况。

当我们遇见这种情况 p[j]==p[next[j]] 的情况，我们只需要执行递归 next[next[j]]，直到不相等为止，下面让我们看看代码如何去实现。

代码的实现

使用方法与next数组的使用方法一致，这里不过多赘述了。