欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

经典算法之KMP算法

程序员文章站 2022-05-02 17:39:46
...

简介

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

  • 题目展示

    • 给出两个字符串s1(主串)和s2(模式串),判断s2是否是s1的子串.
    • 输入两行
      • 第一行:主串s1
      • 第二行:模式串s2
    • 输出第一个匹配的位置(下标),若s1不包含s2子串,输出-1。

      • 主串s1:ababcababeaf
      • 模式串s2:ababe 模式串s2:ababecf
      • 输出:5      输出:-1
  • 吐槽一下:KMP算法代码实现简单,但理解起来比较困难,博主学习第一遍的时候以为领略到了精华,然一切皆是假象,又反过头重新来过,牛掰的算法值得记录一下。

笨方法解读

  • 从主串s1中匹配模式串s2,我们从左至右依次以s1的每个字符为起点匹配。

    • 情况一:在主串s1中可以找到与模式串s2相匹配的子串,遇到s2的结尾停止循环。
    • 情况二:设当前位置为i1,主串s1当前位置到结尾的长度等于模式串的长度(len(s1)i1+1==len(s2)),且主串s1当前位置字符不等于模式串s2首位置字符(s1[i1]!=s2[0]),直接返回1。原因:此后s1的子串长度小于s2的长度,肯定不能匹配。
      经典算法之KMP算法
  • 代码段

#include<iostream>
#include<string>

using namespace std;

int getIndexOf(const string& s1, const string& s2) {
    int len1 = s1.length();  //主串长度
    int len2 = s2.length();  //模式串长度
    int i1 = 0,i2 = 0; //下标遍历
    while (i2 != len2) {
        if (s1[i1] == s2[i2]) {
            ++i1;
            ++i2;
        }
        else {
            if (len1 == len2)
                return -1;
            else {
                i1 = i1 - i2 + 1;
                i2 = 0;
                --len1;
            }
        }
    }
    return i1 - i2;
}

int main(int argc, char* argv[]) {
    string s1; //主串
    cin >> s1;
    string s2; //模式串
    cin >> s2;
    int index = getIndexOf(s1, s2);
    index == -1 ? cout << "no" << endl : cout << "yes" << endl;
    getchar();
    return 0;
}

KMP算法

  • 采用笨方法解读时,我们会发现主串s1中的某些下标根本无需与模式串s2匹配,图解示意如下。第(3)、(4)步的匹配是可以省略的,可直接跳到主串s1下标为2的位置往下匹配,这时KMP就登场了。
    经典算法之KMP算法

  • 字符的最长前缀和最长后缀

    • 最长前缀不包括最后一个字符
    • 最长后缀不包括第一个字符
    • 从前往后加字符形成前缀,从后往前加字符形成后缀。对于字符串s=”abcabe”的字符‘e’,最长前缀为”abca”,最长后缀为”bcab”。
      • 前缀为a,后缀为b时,”a”!=”b”
      • 前缀为ab,后缀为ab时,”ab”==”ab”
      • 前缀为abc,后缀为cab时,”abc”!=”cab”
      • 前缀为abca,后缀为bcab时,”abca”!=”bcab”

        经典算法之KMP算法
  • next数组

    • next数组是KMP算法的精髓所在,数组长度与模式串s2的长度相等,下标中存储的值为模式串s2相对应字符的(前缀==后缀)时的长度。
    • 第一个字符无前缀和后缀,因而默认为1
    • 第二个字符前面只有一个字符,不满足最长前缀不包括最后一个字符,最长后缀不包括第一个字符的条件,因而默认为0
    • next数组其他下标存储的值我们采用图形来理解。
      • 情况一: s[i]==s[j],当前下标存储的值为上一个下标存储的值加1。为什么呢?因为如果可以加2加3,说明之前求取的(前缀==后缀)的最长长度是错误的。
        经典算法之KMP算法
      • 情况二:s[i]!=s[j]。
        • 第(3)步相等:next[j+1]=next[i]+1。
        • 第(3)步不相等:循next[i]的下标继续比较,直到存储的值为-1为止,即长度为0。
          经典算法之KMP算法
  • 代码段

void getNextArray(string s2, vector<int>& next) {
    int len = s2.length();
    if (len == 1) {
        next[0] = -1;
        return;
    }
    next[0] = -1;
    next[1] = 0;
    int cn = 0; //前缀的标志
    int i = 2;
    while (i < len) {
        if (s2[i - 1] == s2[cn]) {
            next[i++] = ++cn;
        }
        else if (cn > 0) {
            cn = next[cn];
        }
        else {
            next[i++] = 0;
        }
    }
    return;
}
  • KMP算法演示
#include<iostream>
#include<string>
#include<vector>

using namespace std;

void getNextArray(string s2, vector<int>& next) {
    int len = s2.length();
    if (len == 1) {
        next[0] = -1;
        return;
    }
    next[0] = -1;
    next[1] = 0;
    int cn = 0; //前缀的标志
    int i = 2;
    while (i < len) {
        if (s2[i - 1] == s2[cn]) {
            next[i++] = ++cn;
        }
        else if (cn > 0) {
            cn = next[cn];
        }
        else {
            next[i++] = 0;
        }
    }
    return;
}

int getIndexOf(const string& s1, const string& s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    if (len1 < 0 || len2 < 0 || len1 < len2) {
        return -1;
    }
    int i1 = 0, i2 = 0;
    vector<int> next(len2);
    getNextArray(s2, next);
    while (i1!=len1 && i2!=len2) {
        if (s1[i1] == s2[i2]) {
            ++i1;
            ++i2;
        }
        else if (next[i2] == -1) {
            ++i1;
        }
        else {
            i2 = next[i2];
        }
    }
    return i2 == len2 ? i1 - i2 : -1;
}

int main(int argc, char* argv[]) {
    string s1; //主串
    cin >> s1;
    string s2; //模式串
    cin >> s2;
    int index = getIndexOf(s1, s2);
    index == -1 ? cout << "no" << endl : cout << "yes" << endl;
    getchar();
    return 0;
}
相关标签: KMP算法