KMP算法的图解_kmp算法图解

前言:
之前在学数据结构时对于各自算法以及数据结构都是头次接触，以至于当第一次看见KMP时，在苦读一天的各自KMP详解之后还是觉得KMP生涩难懂，如果便作罢。可再过了一年后，习惯leetcode上刷题后，又一次碰到KMP，这一次便打算彻底搞懂它，在半天(时间意义上)的思索后，便有了这次的文章。

1.KMP算法核心
与其他解析一开始就从0开始解析它不同，我选择从KMP中最核心的部分讲解，这样有便于快速入手而不会迷失在其他无关紧要的东西上(相对来说)。在开始之前我们先假设一个字符串s[0:m]，方便我们之后的叙述。
我们现在需要掌握的主题时，一个字符串的前缀函数。我们先通过一张图来了解什么前后缀的概念，如下:

其中黄色部分称为真前缀，青色部分称为后前缀，可以看出这两段子串相等,即长度相等，对应字符相等。因此对于s,若存在这种前后缀关系，则一定存在j(0≤j ≤m)，使得s[0:j] = s[m-j+1:m]。
我们观察j的取值可以知道，其前后缀可以为本身，但这样的话，对于我们即将所说的kmp解法是无意义的，因此排除这种情况，所以最大前后缀的长度最多为m，如下图所示:

提到这个是想提醒读者，前后缀可能重叠，但不会完全重叠。

接下来我们引入前缀函数的概念，对于0≤i≤m，π(i)表示子串s[0:i]的最长真前缀长度(注意关键字最长)，针对上面这张图，即π(3)=3。而对于i=0的情况(即子串长度为1)根据前后缀不能完全重合的规则我们规定π(0)=0。
真正开始难的部分(核心的部分)是，对于s的每一位i，我们如何求得s[0:i]的π(i).
在此之前我们需要了解π函数的两个性质:
1.如果s[i]=s[π(i - 1)],则π(i)=π(i-1)+1
这个性质看起来晦涩难懂,但我们可以通过图很好的解释:

因为s[2]=s[6],所以π(6)=3.

2.π(i)≤π(i−1)+1
上面性质1的情况是s[i]=s[π(i-1)],但假如两者不相等呢,请看图

那我们现在考虑的是,
π(6)是否可以大于两者相等情况下的π(6),即3.答案显然是不可能的.我们可以用反证法,假设我们找到这么个j,他使得π(i)(即s[0:j])>π(i-1)+1,那如果我们将s[i]这个字符舍弃,则s[0:i]变成了s[0:i-1],那么s[0:i-1]相应的π(i-1)=π(i)-1,但是我们可是假设的π(i)(即s[0:j])-1>π(i-1),这说明我们的π(i)极限值为π(i-1)+1,如果当前
s[i]!=s[π(i-1)]的话,那π(i)≤π(i - 1).

前缀函数π的计算:
1.从性质一我们知道了如何在s[i]=s[π(i-1)]的情况下,计算π(i)的值.
现在我们要知道的是,在s[i]≠[π(i-1)]的情况下,如何计算π(i).

2.首先我们根据性质2,已经提前知道π(i)的前后缀只能是黄色部分的子串.
而KMP算法的答案是这样的,如图,若s[i]≠[π(i-1)],则我们将目光转向s[0:i-1]的真前缀(黄色部分),在这个子串我们继续找它的真前缀(橙色部分),若橙色部分的前缀后一个字符?=d的话,那我们也就找到π(i)=橙色部分长度+1.
π(i)有可能再长一点吗?不可能,因为根据前缀函数的定义,我们已经保证了橙色部分是黄色部分中最大的真前缀了.

前缀函数计算过程

通过前面的推导,我们已经知道如何求得π(i)了,我们可以看出,π(i)的计算是迭代的,我们总是可以在形如s[i]=s[π(*-1)]的情况下可以确定π(i)的值.最后我们来聊一下特殊情况,我们迭代的过程在什么时候停止呢,答案是,在j=0,的时候就不能继续了,如图:

结合字符串匹配问题
1.其实至此我们已经知道怎么计算子串needle(长度为m),在母串haystack(长度为n)第一次出现位置的下标了,我们可以记字符串str=needle+#+haystack,我们用并不存在的字符#将两串分开.
我们从str的左端开始计算前缀函数,因为#的存在,当我们计算到haystack部分时,我们的π(i)(m+1≤i≤m+n)的最大值不会超过m,且真前缀一定在needle前半部分,真后缀一定在haystack中,当π(i)=m时,证明我们已经找到一个真后缀刚好等于needle,如图:

当我们一旦处理到π(i)=m时,我们即可通过下标i找到子串第一次出现的下标i-m+1.

2.优化

1. 为避免字符串赋值与拼接带来的时间和空间上消耗我们不用显示创建字符串str.
2. 我们不用保存str的前缀函数结果,只需保存needle部分的结果.而在haystack部分我们只需要一个常量保存当前π(i)的结果,若π(i)=m,即可返回答案.(不用记录haystack的π是因为我们显然不会用到haystack的π,其原因是因为我们加入#,π(i-1)不可能大于m)
3. 不用处理特殊字符#,我们只需要在处理到haystack第一个字符时,将π(i-1)置为0即可(因为若我们单独处理#时的π(i),因为#不会出现在needle中,则π(i)=0,而在处理下一个字符时当前π(i)也就成了π(i-1),其值为0)

代码实现:

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m]; //pi即为我们的前缀函数
        
        //先处理needle部分
        for (int i = 1, j = 0; i < m; i++) { //j即为π(i - 1)的值
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        //再处理haystack部分
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1; //不存在
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

代码部分自行好好理解

总结

KMP的核心在于掌握前缀函数的求解,以及理解代码每一步背后的语义.其中迭代时j的语义一直都是s[i-1]的最长真前缀后一个字符的下标(除特殊情况j=0),每次迭代将其与s[i]比较得出当前π(i).