KMP算法

KMP算法,快速模式匹配算法,是在暴力匹配的基础上进行的优化。
给定两个串,一个称为主串,另一个称为模式串,我们要在主串里找到一个连续的字串和模式串匹配。
该算法通过一个next数组进行记录,从而优化指针的移位,降低时间复杂度。
对于不同的人对next的定义略有不同,但核心思想都是一样的,掌握KMP算法的思想尤为重要。

前置知识:前缀与后缀

一个字符串的前缀与后缀都是字符串。
如:ABCDEFG这个字符串,它的前缀和后缀字符串的长度是相同的,如下:

字符编号:
A B C A B
0 1 2 3 4
长度:1
A
B
长度:2
A B
A B
长度:3
A B C
C A B
长度:4
A B C A
B C A B
长度:5
A B C A B
A B C A B

对于模式串的next数组,就是要求每一个字符之前的字符串的前缀和后缀的最长匹配。
但是注意,我们这里使用一个静态的串来演示前缀和后缀,而在下面的计算中实际上是通过指针的移位实现一个动态变化,当匹配成功时前缀和后缀的长度都加一,指针向一个方向移动,而非向上面那样指针相向移动。

next数组

定义

next数组的下标和模式串字符下标是一一对应的,存储的值是 当前下标之前的字符串 的 前缀和后缀的最长匹配。

过程推演

暴力匹配

Step1 实时记录一个匹配长度len以及指向模式串和主串的指针
Step2 如果当前字符匹配,模式串和主串的指针以及长度len均+1
Step3 如果失配,则模式串的指针和len重置为0,然后重复Step2,直到再次失配,此时的len即为模式串和字串匹配的最长长度。

next数组优化

一些约定和解释
  1. 模式串当前指针指向的下标为i+1(即待匹配字符)
  2. len表示当前匹配成功的长度
  3. s1表示待匹配字符之前的字符串,这个字符串在主串里长度为len,在模式串中为s[0~i]
  4. 通过调用next[i+1]我们可以知道:对于s1,长度为next[i]的后缀和长度为next[i]的前缀是完全一样的,并且前缀字符串的结尾下标是next[i]-1。
过程

Step1 实时记录一个匹配长度len以及指向模式串和主串的指针
Step2 如果当前字符匹配,模式串和主串的指针以及长度len均+1
Step3 如果失配,“回溯“到对应的前缀字符串的末尾,len更新为next[i],进行Step 4
Step4 前缀字符串的下一个字符与待匹配字符进行匹配,成功则重复Step 2,如果失配重复Step 3直至next数组的值为0.

next数组的使用及初始化

next[i]是待匹配字符的下标
next[i]-1表示前缀字符串的结尾
我们使用next数组目的是找到前缀字符串的下标,但因为next数组存储的是长度,我们在调用时next[i]-1表示前缀字符串的结尾,next[i]是待匹配字符的下标,在使用时需要注意。
当next[i]=0的时候即为没有任何匹配,我们需要提前初始化next[0]为0,表示无法匹配。
在其他的不同教程或者博客中,有些next数组的定义为前缀和后缀的最长匹配-1,即前缀字符串的结尾下标,两种定义大同小异,只需要使用上灵活处理即可。

计算next数组

回顾刚才的暴力算法,我们实时维护了一个len,如果模式串和主串都是同一个字符串,那么这个len就是 当前下标之前的字符串的前缀和后缀的最长匹配,也就是next数组的值。
既然是计算len,我们可以结合前面的next优化:我们在计算next数组的过程中可以通过next数组进行优化计算了,但是要注意初始化问题。
合理性分析:因为计算next数组只会向前移动去寻找next数组的值,假设当前计算next[i+1],那我们只会用到next[0]~next[i]的值,而这些值均是已经计算出来的值。
结论:进行计算next数组的过程和进行字符串匹配的过程是一样的,区别在于计算next数组的模式串和主串是相同的,而匹配是两个不同字符串进行匹配。

实现步骤

我们可以设l和r两个指针,初始化为l=0,r=0,其中l-1代表最长匹配的结尾下标,l表示最长匹配长度,同时也代表待匹配字符,r表示待计算next的字符的下标。
判断s[l]是否等于s[r]来区分两种情况

继承最长匹配

如果相等则说明最长匹配可以拓展,则next[r]=next[l]+1此时l++和r++,继续判断下一位。

“回溯”寻找最长匹配

如果不相等则说明不匹配,需要向前“回溯”寻找匹配的字符串。
回溯过程实际上是l指针前移的过程,令l=next[l]来实现向前移动,直到s[l]==s[r]继承最长匹配,或者是l==0到无法继承next[r]=next[l]+1。

前移操作的合理性

因为待匹配字符之前的 模式串的前缀 和 主串的后缀 是相等的,因此,我们只需要判断前缀和后缀之后的一位是否相等即可。
我们的判断条件是s[l]==s[r],l和r的意义上文已经解释了,可以发现l和r就是模式串的前缀和后缀的后一位。

代码实现

代码中l初始化为0,r初始化为1。
我们的目的是计算前缀和后缀字符串的最长匹配,如果将r初始化为0,因为next数组比较的两个串是一样的,最后会一直成功匹配,next成为一个递增的序列,而不是如我们想的一样得到最长匹配。
为此我们将r初始化为1,这样实际上是默认从一个长度为2的字符串开始匹配,直到找到第一个与前缀匹配的情况。

int next[N]={0};
void calnext(char s[])
{
    int len=strlen(s);
    int l=0,r=0;
    for(r;r<len;r++)
    {
        while(l!=-1&&s[r]!=s[r])
        {
            l=next[l];
        }//不停向前回溯的过程
        if(s[r]==s[l])
        {
            l++;//如果最终都不匹配,则j不变仍为-1
        }
        next[r]=l;
    }
}

r++放在了for里,l++因为只有匹配成功才会变化,所以放在了if里。

完整KMP算法实现

KMP算法的第一步是计算模式串的next数组,然后再进行匹配。
整体过程和next一样,但区别在于l和r的初始值,均为0,因为这里就是要找完全匹配,所以不需要特殊处理。

int next[N];
void cal_next(char s[]);
bool KMP(char text[],char s[])
{
    cal_next(s);
    int len=strlen(text);
    int m=strlen(s);
    int l=0;
    for(int r=0;r<len;r++)
    {
        while(l&&text[r]!=s[l])
        {
            l=s[l];
        }
        if(text[r]=s[l])
        {
            l++;
        }
        if(l==m)
        {
            return 1;
        }
    }
    return 0;
}

如果要统计模式串在字串中出现的次数,只需要增加一个cnt统计j==m的次数并返回这个次数即可。
注意,在进行cnt++之后j需要前移到next[j],这是因为可能出现重叠的情况,如果不考虑重叠,让j=-1即可

参考内容:

[1].

[2]KMP算法(快速模式匹配算法)C语言详解 (biancheng.net)

暂无评论

发送评论 编辑评论


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