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

Sababa
PM00123

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

Sabcac
PM00010

通过公式计算移动位数

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

第一趟

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

Sabcac
PM00010
NEXT-10001

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

Sabcac
NEXT01112

此时就十分方便了:
在字串第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.$

计算next相关代码

隐藏资源
此处内容需要 评论本文 后才能查看, 评论后请刷新本页面.

最终项目实现代码

隐藏资源
此处内容需要 评论本文 后才能查看, 评论后请刷新本页面.

执行结果

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

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

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

'aaaab'与'aaabaaaaab'进行匹配时
主串(s)aaabaaaaab
模式(p)aaaab
j12345
next[j]01234

当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数组的使用方法一致,这里不过多赘述了。

广告 广告位招租

评论

  1. jopp
    Android Chrome
    中国北京市北京
    11月前
    2022-1-23 16:11:31

    回复查看代码

  2. dadaq
    Windows Chrome
    中国北京市北京
    11月前
    2022-1-18 12:13:09

    让我康康

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
小黄脸
上一篇
下一篇