MENU

KMP算法的实现及其优化

April 8, 2020 • Read: 601 • 算法

于2020.4.8日重写

kmp算法的实现有多种方式,我这里讲两种:
传统写法以及确定有限状态机版
有限状态机版待修改

kmp算法简介

KMP 算法是一种改进的字符串匹配算法,由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 提出的,因此人们称它为克努特莫里斯普拉特操作(简称 KMP 算法)。KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next () 函数实现,函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度 O(m+n)。 ——摘自百度百科

在普通的字符串匹配算法中,我们可能会使用两个for循环来不停的匹配字符串,直到完全匹配完为止,就是类似于如下的一种写法:

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-04-08 13:43:16
 * @Website1: 449293786.site
 */
#include<bits/stdc++.h>
using namespace std;
int search(string cmp,string pattern)
{
    int i=0,j=0;
    while (i<cmp.length()&&j<pattern.length())
    {
        if (cmp[i]==pattern[j])
        {
            i++,j++;
        }
        else
        {
            i=i-j+1;
            j=0;
        }
    }
    if (j=pattern.length())
    {
        return i-j+1;
    }
    return -1;
}
int main()
{
    string cmp,pattern;
    cin>>cmp>>pattern;
    cout<<search(cmp,pattern)<<endl;
    return 0;
}

这就是比较常用的幼稚算法,时间复杂度差不多O(n^2),用的也比较广,如果没有记错的话,java内置的find()函数好像也是用这样实现的……对此我不做任何评价

一、传统写法

然后是kmp算法的传统写法,这个算法的核心就是利用模式字符串pattern求出一个next数组,然后利用这个数组进行匹配,优点是待匹配字符串不必再回溯,可以直接扫描一遍就过,时间复杂度为O(n),具体工作方式如下图

转自知乎https://zhuanlan.zhihu.com/p/83334559

从图中我们可以看出,i指针并没有回退,而是一次性扫描就结束,利用已经部分匹配的这个有效信息,保持i指针不回溯,通过修改模式字符串指针,让模式字符串尽量移动到有效的位置,这也正是kmp算法的神奇之处。

我们先抛开复杂的next数组,首先看看匹配函数

search()函数

search函数和暴力写法比较类似

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-04-08 13:10:56
 * @Website1: 449293786.site
 */
int search(string cmp, string pattern)
{ 
    if(pattern == "") 
        return 0; 
    int* next = get_next(pattern);
    int i=0;//待匹配字符串指针
    int j=0;//模式字符串指针
    while(i <cmp.length() && j <pattern.length())
    {
        if(j == -1 || cmp[i] == pattern[j])
        {
            i++;j++;
            //匹配成功或者模式指针被回退到了-1
        }
        else
        {
            j = next[j];
            //匹配失败,模式指针回退到next[j]
        }
    }
    if(j == pattern.length())
    {
        //模式指针走完全程,匹配成功
        return i-j; 
    }
    else
    {
        //匹配失败,返回-1
        return -1; 
    }
}

或许你看了代码又开始疑惑了,这next数组是啥呢?它咋知道该回退到哪个位置呢?不要心急,待我慢慢道来

next数组

这里我们先做一个约定:

i为待匹配字符串指针,j为模式字符串指针

这个数组是为了实现让待匹配字符串指针不回溯,只让模式字符串指针回退的工具,也是kmp算法最核心的部分,很多的算法书在这里都是一笔带过,确实让读者比较难受,所以我决定这里讲细一点

next数组记录了啥?

确切的来说,next数组记录的是这个字符失配后,模式字符串指针应当回退到的位置

next数组怎么计算?

我们先来观察一下kmp算法的匹配规律

情形1:

在CD时发生了失配,于是j开始回溯

回溯后继续开始匹配

情形2:

在CD时发生失配

17084030-82e4b71b85a440c5a636d57503931415

开始回溯

17084037-cc3c34200809414e9421c316ceba2cda

我们仔细观察一下两种情形:
情形1中发生失配,j指针回溯到了1号位(从0号位开始)
情形2中发生失配,j指针回溯到了2号位

那我们猜想,是不是和模式字符串中的什么东西有关呢?凭借这种猜想,我们来观察一下两个模式字符串:
ABAD,其中发生失配的D前面,有ABA,其中A和A是一样的,长度为1
ABCABB,其中发生失配的B前面,有ABCAB,其中AB和AB是一样的,长度为2

我们把相同的这一段分别叫做公共前缀和公共后缀,而失配后回溯的位置刚好是公共前后缀的长度

17084056-66930855432b4357bafbf8d6c76c1840

我们规定零号为上的值为-1,利用这个性质,我们可以来试着求一下next数组

假如有如下pattern(模式)字符串:

ABABABB -> -1 0 0 1 2 3 4
ABAB -> -1 0 0 1
AAAB -> -1 0 1 2

接下来的问题就是如何利用代码计算next数组了

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-04-08 14:52:57
 * @Website1: 449293786.site
 */
#include <bits/stdc++.h>
using namespace std;
int* get_next(string pattern)
{
    int* next = new int[pattern.length()];
    //动态申请一段空间
    next[0] = -1;
    //将next数组初始化
    int i = 0;//模式字符串指针
    int k = -1;//记录最大公共前缀长度
    int size = pattern.length();
    while(i<size - 1)
    {
        if(k == -1 || pattern[k] == pattern[i])
        {
            //如果匹配上了,公共前缀长度增加
            i++;k++; next[i] = k;
        }
        else
        {
            //如果失配了,改变公共前缀的长度
            k = next[k];
        }
    }
    return next;
}

int main()
{
    string pattern;
    cin>>pattern;
    int *next=get_next(pattern);
    for (int i=0;i<pattern.length();i++)
    {
        cout<<next[i]<<" ";
    }
    return 0;
}

这里再解释一下k=next[k]

17122439-e349fed25e974e7886a27d18871ae48a

当我们找不到abab这个最大的后缀串的时候,我们可以找到ab,b这样的前缀串,这个过程就可以直接从next[k]里面取得

传统版本代码:

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-04-09 09:39:32
 * @Website1: 449293786.site
 */
#include <bits/stdc++.h>
using namespace std;
int* get_next(string pattern)
{
    int* next = new int[pattern.length()];
    next[0] = -1;
    int j = 0;
    int k = -1;
    int size = pattern.length();
    while(j<size - 1)
    {
        if(k == -1 || pattern[k] == pattern[j])
        {
            j++;k++; next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
    return next;
}
int KMP(string cmp, string pattern)
{
    if(pattern == "") return 0;
    int* next = get_next(pattern);
    int i=0;
    int j=0;
    while(i < int(cmp.length()) && (j < int(pattern.length())))
    {
        if(j == -1 || cmp[i] == pattern[j])
        {
            i++;j++;
        }
        else
        {
            j = next[j];
        }
    }
    if(j == pattern.length())
    {
        return i-j;
    }
    else
    {
        return -1;
    }
} 
int main()
{
    string cmp,pattern;
    cin>>cmp>>pattern;
    int location=KMP(cmp,pattern);
    cout<<location<<endl;
    return 0;
}
传统代码分析:

当出现如下情形的时候

17084712-f0d6998938764b309f61923452a2b20f

17084726-790fc1b2c48c411b8011eab9de692f6d

这一步完全就没有意义了,因为CB是不能匹配的,所以我们添加一个判断条件:P[j] == P[next[j]]

传统代码升级版

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-04-08 12:31:30
 * @Website1: 449293786.site
 */
#include<bits/stdc++.h>
using namespace std;
int* get_next(string pattern)
{
    //get next array and return a point
    int size=pattern.length();
    int* next=new int[size];
    //动态申请一块空间
    next[0]=-1;
    //给零号位初始化为-1,当零号位不能匹配时整体后移一位
    int j=0,k=-1;
    while (j<pattern.length()-1)
    {
        if (k==-1||pattern[j]==pattern[k])
        {
            if (pattern[++j]==pattern[++k])
            {
                next[j]=next[k];
            }
            else next[j]=k;
        }
        else k=next[k];
    }
    return next;
}

int KMP(string cmp, string pattern)
{ 
    if(pattern == "") 
        return 0; 
    int* next = get_next(pattern);
    int i=0;
    int j=0; 
    int cnt=0;
    while(i < int(cmp.length()) && (j < int(pattern.length())))
    {
        if(j == -1 || cmp[i] == pattern[j])
        {
            i++;j++; 
        }
        else
        {
            j = next[j];
        }
        cnt++;
    }
    cout<<"cnt="<<cnt<<endl;
    if(j == pattern.length())
    {
        return i-j; 
    }
    else
    {
        return -1; 
    }
}

int main()
{
    string cmp,pattern;
    int number1,number2;
    cin>>cmp>>pattern;
    cout<<KMP(cmp,pattern);
    return 0;
}

二、确定有限状态机

说实话,这种算法严格意义上来说不应该是kmp算法,但是他的核心却又和kmp算法类似,里面又参和了点DP的味道,确实挺不错的,但是空间复杂度却比传统kmp算法大O(n^2)

先看一下这种算法的大概结构:

void get_next(string pattern)
{
    //通过pattern构建next数组
}
void kmp(string cmp)
{
    //借助next数组来匹配cmp
}

我先大致解释一下状态机:

v2-64af121ef2a1eda9c31dcc77074a390f_720w

在这张图里,圆圈内的数字就是状态,0是起始状态,5是终止状态,开始匹配时,pattern处于起始状态,一旦匹配到终止状态,就说明匹配成功

接下来我们看几个例子

当待匹配字符串已经完成了ABAB四个字符的匹配,接下来的状态,是由待匹配字符串的下一位决定的

v2-0e8847ed6b179f4869c229c6ece5e127_720w

如果下一位是A,那么pattern就转换到状态3

v2-dfcb10125f920a140c1dcfb22c3772a7_720w

如果下一位是B,就要打回去重新做人(我jojo不做人啦!!!)

v2-e9462a046f83aeeac19f8df3d5de2e57_720w

如果下一位是C,那么就转移到状态5,即终止状态,字符串匹配完毕

v2-134e0fa9c0f4bab1c1d92f901fc8a229_720w

当然,如果遇到的是其他字符,也应当转换到状态0去

然后,经过一系列神奇的变化,就有了:(怎么求接下来讲,小伙伴们不必心慌)

v2-908bc4e357981fe7c987781125d4cde0_720w

嗯……简直清晰……

再看看这种算法的核心,仔细理解这个图

v2-aaa16eea8cf11b2957d207c249a49276_b

next数组怎么计算?

next[j][c]=next_status
0 <= j < M,代表当前的状态
0 <= c < 256,代表遇到的字符(ASCII 码)
0 <= next_status <= M,代表下一个状态

next[4]['A'] = 3 表示:
当前是状态 4,如果遇到字符 A,
patttern 应该转移到状态 3

next[1]['B'] = 2 表示:
当前是状态 1,如果遇到字符 B,
patttern 应该转移到状态 2

因为我们已经确定了next数组的含义,所以定义next数组的时候就有如下的框架:

for 0 <= j < M: # 状态
    for 0 <= c < 256: # 字符
        dp[j][c] = next

如果遇到的字符能够和pattern[i]匹配,则状态向前推进
否则就保持原地不动或者回退,我们称为状态重启

v2-191926a0e5f839222cfb54d807a5c001_720w

状态重启↓↓↓

v2-0e6ead5b5744d8b26cf43959da1b1053_720w

那么,怎么确定重启的位置呢?

这里要引进一个新的名词:影子状态
指的是和当前状态具有相同的前缀,(其实就类似于最大公共前缀和最大公共后缀了)

v2-c7b0501a11e937d9d97a201762214e4d_720w

当前状态j=4,其影子状态为x=2,他们都有相同的前缀“AB",因为状态x和j存在相同的前缀,所以,当状态j准备重启的时候,会来问问x,x会告诉他应该会到哪里

比如:当j遇到字符”A",他应当转移重启到哪里呢?状态j回来问问x,就是next[j]['A']=next[x]['A'],而x中已经提前算好了应当回退到哪个位置v2-c213fc269f594a6cccda3d16300be1c2_720w

为什么呢?
kmp中,为了减少不必要的计算,j就应该去找和自己有相同前缀的x:如果x遇见“A”,该回退到哪个位置。这样转移过去,才能使回退最少,j只需要跟着x走就行了

v2-75fb3a0b7f07e1906ad3a11ac7c54a20_b

接下来再细化一下代码框架:

int X # 影子状态
for 0 <= j < M:
    for 0 <= c < 256:
        if c == pat[j]:
            # 状态推进
            dp[j][c] = j + 1
        else: 
            # 状态重启
            # 委托 X 计算重启位置
            dp[j][c] = dp[X][c]

最后,给出确定有限状态机版本的方程:

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-04-08 13:08:01
 * @Website1: 449293786.site
 */
#include<bits/stdc++.h>
using namespace std;
int next1[100][256];
void get_next(string pattern)
{
    int shadow=0;
    int size=pattern.length();
    next1[0][pattern[0]]=1;
    for (int i=1;i<size;i++)
    {
        for (int j=0;j<256;j++)
        {
            next1[i][j]=next1[shadow][j];
        }
        next1[i][pattern[i]]=i+1;
        shadow=next1[shadow][pattern[i]];
    }
}
int search(string cmp,string pattern)
{
    int size_pattern=pattern.length();
    int size_cmp=cmp.length();
    int j=0;
    for (int i=0;i<cmp.length();i++)
    {
        j=next1[j][cmp[i]];
        if (j==size_pattern)
            return i-size_pattern+1;
    }
    return -1;
}
int main()
{
    get_next("sip");
    cout<<search("missisasipi","sip");
    return 0;
}

难为死我了……

文章参考&图片来源(实在太懒不想自己手动画图……):

https://zhuanlan.zhihu.com/p/83334559

https://www.cnblogs.com/yjiyjige/p/3263858.html

Last Modified: April 22, 2020
Archives Tip
QR Code for this page
Tipping QR Code