KMP 算法示例和解析（2)_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
北京抗疫模式渐渐落入上海之俗套！
是记。