Eswlnk

一个有点倒霉的小站长

IP归属地：四川

文章

1.0k

263

友情链接

Eswlnk

2022-08-20 15:46:08 四川

「代码发布」实现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

S	a	b	a	b	a
PM	0	0	1	2	3

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

S	a	b	c	a	c
PM	0	0	0	1	0

通过公式计算移动位数

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

第一趟

主串 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 数组:

S	a	b	c	a	c
PM	0	0	0	1	0
NEXT	-1	0	0	0	1

子串移动位数 = 已匹配的字符串数 – 对应的部分匹配值
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方便计算

S	a	b	c	a	c
NEXT	0	1	1	1	2

此时就十分方便了：
在字串第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'进行匹配时

主串(s)	a	a	a	b	a	a	a	a	a	b
模式(p)	a	a	a	a	b
j	1	2	3	4	5
next[j]	0	1	2	3	4

当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]]，直到不相等为止，下面让我们看看代码如何去实现。