请选择 进入手机版 | 继续访问电脑版

三分钟理解KMP算法

[复制链接]
小甜心 发表于 2021-1-2 19:46:02 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
前言:一般的书籍或文章教学KMP算法都是从问题分析、思路教学再到代码教学。但是我以为先看懂代码、再捋清思路反而会更容易,所以本文会以代码+代码分析的方式来教学KMP算法。
一、BF算法的代码

  1. #include #include #include int BF(const char* txt, const char* pat){    int i = 0;    int j = 0;    int txt_len = strlen(txt);    int pat_len = strlen(pat);    while (i < txt_len && j < pat_len)    {        if (txt[i] == pat[j])        {            i++;            j++;        }        else        {            i = i - j + 1;            j = 0;        }    }    if (j == pat_len)    {        return i - j + 1;    }    return -1;}int main(){    char txt_str[101];    char pat_str[11];    puts("Please input main string (Max 100 chars):");    gets(txt_str);    puts("Please input pattern string (Max 10 chars):");    gets(pat_str);    printf("Matched position: %d\n", BF(txt_str, pat_str));    return 0;}
复制代码
二、BF算法没有处理处罚好的地方

当主串的第4个字符和模式串的第4个字符不匹配时:

  • 主串:aaaaaaac,模式串:aaab
    BF算法:从主串的第2个字符和模式串的第1个字符开始向后匹配;
    KMP算法:从主串的第4个字符和模式串的第3个字符开始向后匹配。
  • 主串:aaacaaab,模式串:aaab
    BF算法:从主串的第2个字符和模式串的第1个字符开始向后匹配;
    KMP算法:从主串的第4个字符和模式串的第3个字符开始向后匹配。
可以看到BF算法在字符不匹配时,下一次比对字符的位置会做没有意义的回退。
三、KMP算法的代码

  1. #include #include #include void init_next(const char* pat, const int pat_len, int* next){    next[0] = -1;    int j = 0;    int k = -1;    while (j < pat_len - 1)    {        if (k == -1 || pat[j] == pat[k])        {            j++;            k++;            next[j] = k;        }        else        {            k = next[k];        }    }}int KMP(const char* txt, const char* pat){    int i = 0;    int j = 0;    int txt_len = strlen(txt);    int pat_len = strlen(pat);    int* next = (int*)malloc(pat_len);    init_next(pat, pat_len, next);    while (i < txt_len && j < pat_len)    {        if (j == -1 || txt[i] == pat[j])        {            i++;            j++;        }        else        {            j = next[j];        }    }    free(next);    next = NULL;    if (j == pat_len)    {        return i - j + 1;    }    return -1;}int main(){    char txt_str[101];    char pat_str[11];    puts("Please input main string (Max 100 chars):");    gets(txt_str);    puts("Please input pattern string (Max 10 chars):");    gets(pat_str);    printf("Matched position: %d\n", KMP(txt_str, pat_str));    return 0;}
复制代码
四、KMP算法的处理处罚方式


  • 设主串的长度为n,模式串的长度为m,则BF算法的时间复杂度是O(n*m),空间复杂度是O(1),KMP算法的时间复杂度O(m+n),空间复杂度O(m)。
  • KMP算法分为两步,第一步是构造next数组(由init_next函数实现,时间复杂度为O(m),空间复杂度为O(m)),第二步是顺序逐个字符遍历主串(由KMP函数中的while语句实现,时间复杂度为O(n))。
  • 模式串为aaab时,next数组为{-1, 0, 1, 2}。
  • 变量i指示主串当前比对的索引位置,变量j指示模式串当前比对的索引位置,变量k指示模式串下一次比对的索引位置。
  • next数组的值只与模式串有关,与主串无关,一共pat_len个元素,元素next[j]的值存储的是pat[j]与txt不匹配时下一次与txt比对的pat[k]的模式串索引位置k,k一定比j小。数组中-1和0代表重新从pat[0]开始比对,1代表重新从pat[1]开始比对,2代表重新从pat[2]开始比对,依此类推。
  • next[0]一定便是-1,next[1]一定便是0,next[j]的值只与pat[0]到pat[j-1]这j个字符有关,next[j]的值与pat[j]是什么字符无关。
  • 现在来讲讲next数组的值要怎么确定。字符串的前缀指除最后一个字符以外,字符串的所有头部子串。字符串的后缀指除第一个字符以外,字符串的所有尾部子串。以模式串aaab为例,next[0]和next[1]是固定值,next[2]的值由pat[0]到pat[1]这个字符串"aa"决定,"aa"的前缀为{a},后缀为{a},                                   {                         a                         }                         ∩                         {                         a                         }                         =                         {                         a                         }                              \{a\}\cap\{a\}=\{a\}                  {a}∩{a}={a},{a}中最长的子串的长度为1,故next[2]便是1,next[3]的值由pat[0]到pat[2]这个字符串"aaa"决定,"aaa"的前缀为{a,aa},后缀为{a,aa},                                   {                         a                         ,                         a                         a                         }                         ∩                         {                         a                         ,                         a                         a                         }                         =                         {                         a                         ,                         a                         a                         }                              \{a,aa\}\cap\{a,aa\}=\{a,aa\}                  {a,aa}∩{a,aa}={a,aa},{a,aa}中最长的子串的长度为2,故next[2]便是2。
  • 从代码实现的角度来说,在init_next函数中变量k存储的是当前子串(pat[0]到pat[j-1]这j个字符)的最长相等前后缀的前缀最后一个字符的索引位置,各人可以加一些打印自己跑一下代码。
  • KMP函数中while循环里做的事情就很简朴了。如果当前字符相同,则继续比对下一个字符,如果当前字符差别,则将主串中的当前字符继续与next数组指定的模式串中的字符比对。如果j到达模式串的末端则退出循环(说明已经匹配到了效果),如果i到达主串的末端了j依然没有到达模式串的末端则说明主串中不存在模式串。
五、KMP算法的进一步优化


  • 我们再来思考一种情况,当模式串为abab时:
    原来的KMP算法的next数组:{-1, 0, 0, 1}
    改进后的KMP算法的next数组:{-1, 0, -1, 0}
  • 当txt和模式串的第4个字符’b’不匹配时,老算法会回到模式串的第2个字符’b’开始比对(注意上面两个next数组的第4个元素的差别),改进后的算法会回到模式串的第1个字符’a’开始比对,因为txt既然不便是模式串的第4个字符’b’,那么txt也不会便是模式串的第2个字符’b’。
  • 改进前后next数组的差别都与上面这种原因雷同,许多资料也将改进后的next数组称为nextval数组。
  • 将init_next函数里if语句中的next[j] = k;语句替换为如下代码即可:
    1. if (pat[j] != pat[k]){    next[j] = k;}else{    next[j] = next[k];}
    复制代码

来源:https://blog.csdn.net/CharmingSun/article/details/112080172
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )