当前位置:   article > 正文

KMP 算法示例和解析(2)_kmp算法,k最大取值

kmp算法,k最大取值

本章将就KMP算法递归公式进行推导和解析。
难点:
递归思想在KMP算法推导中的使用

在KMP算法的推导过程中,使用了自己引用自己的递归推导方法,如果对next的定义的物理意义理解不清或者感性认识不足,这个递归的推导就会陷入无穷无尽的思考死循环中。笔者就是这样痛苦了好几天,这个怎么说呢,算是笨吧(虽然我不愿意承认,但事实如此啊)。
好了,直接引用书上的定义,笔者将把自己的理解附上。

KMP算法推导过程

课本上采用数列的递推公式的做法引入了推导过程,原书拍照截图如下:
在这里插入图片描述

在这里插入图片描述

下面对关键句子进行详细解析;
在这里插入图片描述
此句根据前面的定义而来,即位置J的前面存在一个最大的长度为k-1的子串,该子串等于模式串最前面的长度为k-1的子串。
如图:
在这里插入图片描述
在这里插入图片描述
不可能存在 k‘ 的意思是k是最大值,这个是定义过的。

在这里插入图片描述
4-8 不再解释;
4-9 解释如下:
不可能存在K‘>K,仍然指的是 K是最大值;,这样根据定义, 在j+1 前面有个 长度为k的子串,如图:
在这里插入图片描述
因此 next[j+1]= k+1 = next[j] +1

上面是比较容易理解的部分,重点在下面。为了突出之,单列一个小标题。

next函数递推过程详解

首先明确递推过程的目的是查找符合要求的子串,从而确定next(j+1)的函数值,按照定义查找最容易理解,这个在上文中已经根据定义做了推导;但是按照定义去做,方法比较繁琐,而且效率未必会高。这个推导过程的精彩之处有两点,

第一是利用next函数的特点进行推导,可以规范和简化代码,
第二是这个查找速度很快, 比按定义的方式查找快得多。

目的明确之后,我们思考怎么利用next函数来提高查找这个字符串的速度。
在主串中查找模式串的过程中,next[j] 值有两个具体含义:其一是定义的表达,其表达是模式串中相同两个子串的关系;其二是:在主串中在某个失配字符的前面可能存在一个同样长度的子串(这也是诞生kmp算法的基础场景)如图示中的绿色子串。
在这里插入图片描述
模式串中j位置和主串失配后,下一轮比较的位置是上图中下半部所示,k 来自 next(j) (k= next(j))
我们把上图中而主串换成模式串
如图:
在这里插入图片描述

我们的目的:查找j+1 前面的最长配对子串,如果如上图所示,即pk=pj, 那么显然 next[j+1] = k+1,这个和上面的分析是一致的。
如果pk!=pj,根据前面主串和模式串的匹配方式,我们要把(模)主串上的j(相当于主串上的)固定,而移动(模)模式串到k‘(即next(k) 这个k 相当于大模式串中的j)与j对齐的位置上再次进行比较, 如下图:

在这里插入图片描述

如果pj=pk’, 相当于 j +1前面存在一个 k‘ 的子串就是满足要查找的子串。即next(j+1)= k‘+1= next(k)+1
请把上面的过程多看几遍!!!
如果 pj!=pk‘, 则将next[k’]和pj对齐,继续匹配…直到匹配不成功(根据定义的第三条,其他),此时next(j+1)=1.

next函数代码

kmp算法回顾

如果直接看课本上的next函数代码,是很难看懂的。要把KMP算法再复习一遍。课本上给出的代码是Pascal 完成的

FUNC index_KMP(s,t:strtp):integer;
i:=1;j:=1;
WHILE(i<=s.curlen) AND (j<=t.curlen) DO
IF (j==0) OR (s.ch[i]==t.ch[j] {这里对齐并比较}
THEN [i:=i+1;j:=j+1] {继续比较下一对字符}
ELSE j:=next[j];{模式串右移滑动,滑动至next[j] 位置对齐 主串i 的位置}
IF j>t.curlen THEN RETURN (i-t.curlent) {匹配成功}
ELSE RETURN(0)
ENDF;
简析:KMP 算法是比较两个字符串,主串和模式串,比较位置从1 开始;比较不成功后,主串指针不懂,滑动模式串在进行比较。

next 函数的实现

根据next函数的定义以及上一小节的分析,next函数中涉及在模式串中子串的匹配,可以把模式串中查找子串的过程看令是做模式串中查找模式串子串,如课本所说,把模式串也当成主串。对比KMP算法,如果另 s=t=模式串,则可以在模式串中找到自己,因为他们的起点都是1,所以这样是不行的。而next 函数的查找是错位查找的,即 模式串要从主串的第二位开始查找,如果找到则继续;找不到,就要右移滑动模式串,再进行比较。
课本上next函数如下:

PROC get_next(t:strtp; VAR next: ARRAY [1…t.curlen] OF integer);
j:=1;k:=0;next[1]=0;{初始化,注意i,k 的初始值不同,j相当于 Kmp 算法中的 i,k则相当于j}
WHILE j<s.curlen DO
IF (k==0) OR (t.ch[j]==t.ch[k] {这里对齐并比较}
THEN [j:=j+1;k:=k+1]; next[j]:=k;] {根据 4-9}
ELSE k:=next[k];{模式串右移滑动,滑动至next[k] 位置对齐 主串j 的位置,4-11}
ENDP;
C#代码

        private int[] KmpGetNext(string t)
        {
            int[] next =new int[t.Length+1];
            var j = 1;
            var k = 0;
            next[1] = k;
            while (j < t.Length)
            {
                if(k==0 || t.Substring(j - 1, 1) == t.Substring(k - 1, 1))
                {
                    j++;
                    k++;
                    next[j] = k;
                }
                else
                {
                    k = next[k];
                }
            }
            return next;
        }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

说明:由于算法中字符指针都是从1 开始的,因此next数组多定义了一个整数,使用时也从 1 开始。
应该说,上述的算法构造非常巧妙,是递归思想的典型应用。这种设计思路当是吾辈学习的榜样!不由得想说,向前辈致敬!你们太智慧了!

maraSun BJFWDQ
北京抗疫模式渐渐落入上海之俗套!
是记。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/662074
推荐阅读
相关标签
  

闽ICP备14008679号