图解KMP算法

这篇具有很好参考价值的文章主要介绍了图解KMP算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

子串的定位操作通常称作串的模式匹配。你可以理解为在一篇英语文章中查找某个单词是否存在,或者说在一个主串中寻找某子串是否存在。

  1. 朴素的模式匹配算法

假设我们要从下面的主串S = "goodgoogle" 中,找到T = "google" 这个子串的位置。利用朴素的模式匹配算法我们通常需要下面的步骤。

(1):主串S第一位开始,S与T前三个字母匹配成功,但S第四个字母是d而T的是g。第一位匹配失败。如下图所示:浅绿色方块代表匹配成功,红色方块代表匹配失败。

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

(2):主串S从第二位开始,主串S首字母是o,要匹配的T的首字母是g。匹配失败:

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

(3):主串S第三位开始,主串S首字母是o,要匹配的T首字母是g,匹配失败:

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

(4):主串S第四位开始,主串S首字母是d,要匹配的T首字母是g,匹配失败:

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

(5):主串S第五位开始,S与T,6个字母全部匹配,匹配成功:

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

简单来说,朴素的模式匹配算法就是对主串的每一位字符作为子串的开头,与要匹配的子串进行比较,如果匹配不成功,则主串需要回溯到与子串开始匹配的位置的下一个位置。

当子串与主串有较多的相等的字符时,这种算法的效率是极其低下的。例如:

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档
  1. KMP模式匹配算法

如果你忍受不了朴素的模式匹配算法。于是有三位前辈:D.E.Knuth,J.H.Morris和V.R.Pratt发表了一个模式匹配算法,可以大大避免重复遍历的情况,我们把他称之为克努特-莫里斯-普拉特算法,简称KMP算法。

在去理解KMP算法时你需要知道一个字符串的前缀和后缀是什么?

下面以字符串 "google" 为例:

他的前缀集合:{ "g", "go", "goo", "goog", "googl" }。

它的后缀集合:{ "e", "le", "gle", "ogle", "oogle" }。

2.1 KMP算法匹配方式

假设我们要在主串S = "ABBABBABABAAABABAAA" 中查找模式串T = "ABBABAABABAA" 中的位置。

(1):我们发现主串S和子串T的前5个字符均是匹配的,第6个字符是不匹配的。下一步我们肯定不能回溯到主串第二个字符的位置,不然就是在重走朴素的模式算法的道路了。我们观察发现:1:匹配了五个字符中,2:在模式串的左右两端有两个字符子串,他们是完全匹配的。我们称之为最长公共前后缀。

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

(2):移动模式串,使得原来模式串的前缀到达模式串的后缀的位置:

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

这样的移动可以使得重新开始匹配的位置之前的字符,均是匹配的,因为公共前后缀AB是匹配的,并且原来的5个字符也是匹配的,所以将模式串的前缀移动到后缀的位置,与主串的后缀是匹配的。这样移动可以省去部分字符的不必要匹配(这样移动的正确性我们稍后探讨)。

(3):我们发现模式串的移动与主串并没有关系,因为只是将模式串的前缀移动到了模式串的后缀的位置,并且已经匹配的字符与主串肯定是一样的撒。

这时我们对一般情况做出分析:

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

我们现在已经明白了为什么要移动模式串的前缀到后缀的位置,以及这样移动的正确性。

(4):现在我们可以继续匹配一下主串,理解上述的操作:

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

2.2 next数组的手动推导

上面的图解以及分析仅是一个形象化的过程,我们还得将其转化为计算机能够处理的方式。

emm,我们假设存储字符串是从下标为1的位置开始的呢!

下面以具体的例子:主串S = "ABABABAABABAAABABAA",模式串T = "ABABAAABABAA",来分析如何转化成计算机能够处理的方式。

上面分析过,在模式串的移动过程中,与主串是没有关系的,我们只需要分析模式串即可:

模式串的任何一个位置都可能与主串发生不匹配,我们就是要将不匹配之后模式串由前缀移动到后缀的过程抽象成计算机能处理的形式。

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档
kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

我们发现有这样的规律:next数组对应的值是最长的公共前后缀加1。模式串剩余的字符就不再画图分析了,

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

我们将上面的数组取名为next数组,例如:我们发现模式串在与主串比较时,下标为5的位置发生了不匹配,我们只需要查找next[5] 的值,值为:3,就知道下一步是将模式串的3号位与主串的当前位置进行比较。

2.3 next数组的代码分析

/// <summary>
/// 求解next数组
/// </summary>
/// <param name="s"> 模式串的首字符地址 </param>
/// <param name="n"> 模式串的字符个数 </param>
/// <param name="next"> next数组的首元素地址 </param>
void getNext(char* s, int n, int* next)
{
    //遍历模式串
    int i = 1;
    //为next数组赋值
    int j = 0;
    //第一个字符不匹配将编号赋值为0,代表从主串的下一个位置开始比较
    next[1] = 0;
    while (i < n)
    {
        if (j == 0 || s[i] == s[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}

现在我们先以一个具体的例子来看代码是否正确哈,假设模式串为:"abab":

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

next[1] 需要一开始就初始化的哈。用i遍历模式串时,如果j指向的字符与i指向的字符相等,进入if分支,说明最长公共前后缀需要增加1,为什么是增加1呢?因为i一次只能遍历一个字符嘛!如果i指向的字符与j指向的字符不相等的话,进入else分支,令j=next[j],即更新j的位置,将新的j指向的字符与i指向的字符进行比较,看是否相等,不相等继续令j=next[j],直到j指向的字符与i指向的字符相等或者说j为0。为什么j的更新是j=next[j]? 我们下面就来分析原因!

kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档
kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

这下你就能理解求next数组的全部代码啦。

2.4 查找子串的完整代码

下面是字符串从下标为1开始存储时的查找子串的代码。只是以一个具体的例子实践了一下,你只要理解了思路就随便写代码的。这里的代码仅供参考,具体代码还需结合题目具体分析!

/// <summary>
/// 求解next数组
/// </summary>
/// <param name="s"> 模式串的首字符地址 </param>
/// <param name="n"> 模式串的字符个数 </param>
/// <param name="next"> next数组的首元素地址 </param>
void getNext(char* s, int n, int* next)
{
    //i用来遍历模式串,j用来为next数组赋值,并且查找最长公共前后缀
    int i = 1, j = 0;
    //next[1]需要直接赋值
    next[1] = 0;
    while (i < n)
    {
        if (j == 0 || s[i] == s[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}
int main()
{
    char a[10] = " abababde";
    char s[5] = " aba";
    int next[4];
    getNext(s, 3, next);
    //8是主串的长度哈
    for (int i = 1, j = 0; i <= 8; i++)
    {
        while (j && a[i] != s[j+1])
            j = next[j];
        if (a[i] == s[j+1])
            j++;
        //3是模式串的字符个数,相等就代表找到了
        if (j == 3)
        {
            //输出开始匹配的位置
            printf("%d ", i - j + 1);
            //更新j尝试找到更多解
            j = next[j];
        }
    }
    return 0;
}
kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

下面就是字符串从0开始存储的代码,同样的哈,代码版本有很多,重要的是理解思路!

void getNext(char* s, int n, int* next)
{
    int i = 0, j = -1;
    next[0] = -1;
    while (i < n)
    {
        if (j == -1 || s[i] == s[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}

int main()
{
    char a[9] = "abababde";
    char b[5] = "abab";

    int next[5];
    getNext(b, 4, next);
    for (int i = 0, j = 0; i < 8; i++)
    {
        while (j && a[i] != b[j])
            j = next[j];
        if (a[i] == b[j])
            j++;
        if (j == 4)
        {
            printf("%d ", i - j + 1);
            j = next[j];
        }
    }
    return 0;
}
kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档
  1. 小试牛刀

下面的题解法肯定不止一种,kmp算法也不一定是最简单的,但是阔以用来练习kmp算法的!

3.1 旋转字符串

796. 旋转字符串 - 力扣(LeetCode)
题目描述:给定两个字符串, s 和 goal。如果在若干次旋转操作之后,s 能变成 goal ,那么返回 true。
s 的 旋转操作 就是将 s 最左边的字符移动到最右边。
例如, 若 s = 'abcde',在旋转一次之后结果就是'bcdea' 。

用kmp解题的大致思路就是拼接一个字符串到s后面,将goal当成模式串,在拼接后的字符串中查找goal就行。文章来源地址https://www.toymoban.com/news/detail-781019.html

void getNext(char* neddle, int n,int*next)
{
    int i =0;
    int j =-1;
    next[0] = -1;
    while(i<n)
    {
        if(j==-1||neddle[i]==neddle[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}
bool rotateString(char * s, char * goal){
    int lens = strlen(s);
    int leng = strlen(goal);
    if(lens!=leng)
        return false;
    char*str = (char*)calloc(lens*2+1, sizeof(char));
    memmove(str,s,lens);
    memmove(str+lens,s,lens);
    int * next = (int*)malloc(sizeof(int)*(leng+1));
    getNext(goal, leng,next);
    for(int i = 0,j=0;i<lens*2;i++)
    {
        while(j&&str[i]!=goal[j])
            j = next[j];
        if(str[i]==goal[j])
            j++;
        if(j==leng)
        {
            return true;
        }
    }
    return false;
}
kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

3.2 最长快乐前缀

1392. 最长快乐前缀 - 力扣(LeetCode)
题目描述:
「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀(不包括原字符串自身)的字符串。
给你一个字符串 s,请你返回它的 最长快乐前缀。如果不存在满足题意的前缀,则返回一个空字符串 "" 。
void getNext(char*s,int n,int* next)
{
    int i = 0;
    int j = -1;
    next[0] = -1;
    while(i<n)
    {
        if(j==-1||s[i]==s[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}

char * longestPrefix(char * s){
    int len = strlen(s);
    int next[len+1];
    getNext(s,len,next);
    int max = 0;
    if(next[len]>max)
        max = next[len];
    if(max==0)
        return "";
    else
    {
        char* ret = (char*)calloc(max+1,sizeof(char));
        for(int i = 0;i<max;i++)
        {
            ret[i] = s[i];
        }
        return ret;
    }
}
kmp算法图解过程,数据结构与算法,算法,c语言,c++,数据结构,开发语言,Powered by 金山文档

到了这里,关于图解KMP算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构KMP算法详解

    目录 1. KMP算法是什么? 2. KMP算法的由来 2.1 需要要解决的问题 2.2 一开始想到的方法 2.3 KMP算法诞生了 3.KMP算法的详解 4.KMP算法的实现 5.KMP算法的改进 KMP算法是一种改进的字符串匹配算法,即可以 快速的从主串中找到子串的算法 ,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人

    2024年02月12日
    浏览(57)
  • [数据结构] 串与KMP算法详解

    今天是农历大年初三,祝大家新年快乐! 尽管新旧交替只是一个瞬间,在大家互祝新年快乐的瞬间,在时钟倒计时数到零的瞬间,在烟花在黑色幕布绽放的瞬间,在心底默默许下愿望的瞬间……跨入新的一年,并不意味了一切都会朝着更美好,也没有什么会从天而降,我们赋

    2024年02月19日
    浏览(40)
  • 【数据结构】朴素模式匹配 & KMP算法

    🌈 自在飞花轻似梦,无边丝雨细如愁 🌈   🌟 正式开始学习数据结构啦~此专栏作为学习过程中的记录 🌟 子串的定位操作通常称为串的模式匹配,它求的是模式串在主串中的位置,而朴素模式匹配就是一种不断移动主串指针,每一次都和模式串依次进行比较的暴力求解方法

    2024年02月16日
    浏览(44)
  • 数据结构--字符串的KMP算法

    朴素模式匹配算法: 一旦发现当前这个子串中某个字符不匹配,就只能转而匹配下一个子串(从头开始) 但我们可以知道: 不匹配的字符之前,一定是和模式串一致的 color{red}不匹配的字符之前,一定是和模式串一致的 不匹配的字符之前,一定是和模式串一致的 我们可以利用

    2024年02月12日
    浏览(61)
  • 数据结构—串的详细解释(含KMP算法)

    1.1串的定义 串:串是由零个或多个字符组成的有限序列,又叫字符串(其的存储结构包含顺序表存储、单链表存储的形式。) 一般记为s=\\\"a1a2a3....an\\\"(n=0),其中,s是串的名称,用双引号(也可以使用单引号)括起来的字符序列是串的值,注意引号不是串的内容。ai(i=i=n)可以是字母、

    2023年04月09日
    浏览(44)
  • 【夜深人静学数据结构与算法 | 第一篇】KMP算法

    目录  前言:  KMP算法简介: 引入概念: 前缀后缀 前缀表: 简单例子: 暴力遍历: KMP算法:​  KMP算法难点: 总结: 本篇我们将详细的从理论层面介绍一下什么是KMP算法,相对应的力扣刷题专栏里也会有相对应的习题,欢迎各位前往阅读。           KMP算法是一种字符

    2024年02月08日
    浏览(66)
  • 数据结构-串-KMP算法详解(Next数组计算)(简单易懂)

    本文章就专讲kmp,暴力匹配就不讲了(我相信能搜索kmp的,暴力匹配算法应该也都了解过了) 为什么网上那么多讲kmp 我还发文章,很多文章我觉得讲的不是太通俗易懂,大多数我看起来都觉得有些懵逼 提示:以下信息来源百度 KMP算法是一种改进的字符串匹配算法,由D.E.K

    2024年02月06日
    浏览(43)
  • 《数据结构》实验报告四:串的模式匹配(BF算法、KMP算法)

    1、了解 串 的基本概念。 2、掌握 串的模式匹配算法 的实现 。 说明以下概念 1、模式匹配:          串的模式匹配就是 子串的定位运算 。          设有两个字符串 S 和 T ,S为 主串(正文串) ,T为 子串(模式串) 。在主串S中查找与模式串T相匹配的子串,若匹配成功,确定

    2024年02月01日
    浏览(55)
  • 【数据结构】字符串匹配|BF算法|KMP算法|next数组的优化

    字符串匹配算法是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目,本文主要介绍BF算法(最好想到的算法,也最好实现)和KMP算法(最经典的) BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标S的第一个字符与模式串T的第一

    2024年02月04日
    浏览(53)
  • 【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现

    ​ 🌈 个人主页: Sarapines Programmer 🔥  系列专栏: 《数据结构奇遇记》 🔖墨香寄清辞: 墨痕寄壮志,星辰梦未满。 通幽径心凝意,剑指苍穹势如山。 目录 🌞1. 模式匹配的基本概念 🌞2. 模式匹配的解决办法 🎈2.1 暴力匹配(BF)算法 🎈2.2 KMP算法 🤖2.3 BUG记录_KMP算法 1

    2024年02月04日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包