KMP 算法思想

虽然KMP现在根本就不用，但我就是爱考你，你能把我怎么着

---

1 定义

Knuth-Morris-Pratt 字符串查找算法，简称为 KMP算法，常用于在一个文本串 str 内查找一个模式串 pattern 的出现位置，这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。

算法流程

• 假设现在文本串 str 匹配到下标 i 位置，模式串 pattern 匹配到 j 位置；
• 如果 j == -1，或者当前字符匹配成功（即 str[ i ] == pattern[ j ]），令 i++，j++，继续匹配下一个字符；
• 如果 j != -1，且当前字符匹配失败（即 str[ i ] != pattern[ j ]），则令 i 不变，j = next[ j ]。此举意味着失配时，下次匹配时模式串从下标为 next[ j ] 的位置继续与 str[ i ] 进行匹配。

next 数组各值的含义

next数组中的值代表模式串当前字符之前的模式子串中，相同的前缀后缀的长度是多少。如 next [ j ] = k，代表 j 之前的模式子串中有最大长度为 k 的相同前缀后缀。这也意味着在某个字符失配时，该字符对应的 next 值会告诉你下一步匹配中，模式串应该从哪个位置开始匹配，即从 next[ j ] 开始。如果 next[ j ] 等于 0 或 -1，则下一次匹配从模式串的开头开始匹配，若 next[ j ] = k，代表下次匹配模式串从下标为 k 的字符开始匹配。

代码实现

int kmpSearch(char[] str, char[] pattern) {  
    int i = 0;  
    int j = 0;  
    int sLen = str.length;  
    int pLen = pattern.length;  
    while (i < sLen && j < PLen) {  
        // 如果j = -1，或者当前字符匹配成功（即str[i] == pattern[j]），都令i++，j++      
        if (j == -1 || str[i] == pattern[j]) {  
            i++;  
            j++;  
        } else {  
            // 如果j != -1，且当前字符匹配失败（即str[i] != pattern[j]），
            // 则令 i 不变，j = next[j]，next[j]即为 j 所对应的 next 值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

以下图的匹配举例，当 str[ 10 ]跟 pattern[ 6 ]匹配失败时，令 i 不变，j = next[ j ]， 使得 j 从 6 变到 2，即下一次匹配从模式串 pattern[ 2 ]的位置 C 开始。

str[ 10 ]跟 pattern[ 2 ]继续匹配。为什么要从 pattern[ 2 ]的位置开始匹配呢，因为模式串中pattern[ 2 ]前面有两个字符 AB 可以继续跟str[ 8 ]str[ 9 ]对应着。

2 求解步骤

• 寻找前缀后缀中最长公共元素长度

  • 对于 pattern = P₀P₁ …P_j-1P_j，寻找模式串 pattern 中相等且长度最大的前缀和后缀。如果存在 P₀P₁ …P_k-1P_k = P_{j- k}P_j-k+1…P_j-1P_j，那么模式串中有最大长度为 k+1 的相同前缀后缀。注意前缀必须从第一个元素开始，后缀必须以最后一个元素结束。

    如果给定的模式串是 ABCDABD，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：

    模式串的各个子串	前缀	后缀	最大公共元素长度
    A	空	空	0
    AB	A	B	0
    ABC	A,AB	C,BC	0
    ABCD	A,AB,ABC	D,CD,BCD	0
    ABCDA	A,AB,ABC,ABCD	A,DA,CDA,BCDA	1
    ABCDAB	A,AB,ABC,ABCD,ABCDA	B,AB,DAB,CDAB,BCDAB	2
    ABCDABD	A,AB,ABC,ABCD,ABCDA,ABCDAB	D,BD,ABD,DABD,CDABD,BCDABD	0

    模式串	A	B	C	D	A	B	D
    最大前缀后缀公共元素长度	0	0	0	0	1	2	0

    其实所谓最大前缀后缀长度，就是下图蓝色部分的长度

    

• 求next数组

  next 数组考虑的是当前字符之前的模式子串的最长相同前缀后缀，所以通过第1步骤求得各个子串的最大前缀后缀公共元素长度后，只要稍作变形即可：将第1步中求得的值整体向右移动一位，然后将空出来的第一个元素赋值为 -1，如下表格所示：

  模式串	A	B	C	D	A	B	D
  最大前缀后缀长度	0	0	0	0	1	2	0
  next数组	-1	0	0	0	0	1	2

• 根据next数组进行匹配

  若模式串前 j 个字符匹配成功，即 P₀P₁ …P_j-1 匹配成功，而 P_j 匹配失配，则令 j = next [ j ]，模式串从 P_j 的位置继续匹配 。当模式串的子串 P₀P₁…P_j-1 跟文本串 S_nS_n+1, …, S_i-1 匹配成功，但 P_j 跟 S_i 匹配失败时，因为 next[ j ] = k，相当于在已经匹配成功的模式串子串P₀P₁ …P_j-1中有最大长度为 k 的相同前缀后缀，即 P₀P₁ …P_k-1 = P_j-k P_j-k+1…P_j-1，故令 j = next[ j ]，从而让模式串从 P_j 继续匹配，使得模式串的前缀 P₀P₁…P_k-1 对应着文本串 S_i-k S_i-k+1…S_i-1。如下图所示：

  

KMP的 next 数组相当于告诉我们，当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该从哪个位置继续匹配。如模式串中在 j 处的字符跟文本串在 i 处的字符匹配失配时，下一步用模式串next[ j ] 处的字符 P_j 继续跟文本串 i 处的字符 S_i 匹配。

3 解释

3.1 基于最大长度表匹配

由于模式串中首尾可能会有重复的字符，当出现失配时不一定要从模式串第一个字符开始匹配

下面给定文本串 “BBC ABCDAB ABCDABCDABDE”，和模式串 “ABCDABD”，现在要拿模式串去跟文本串匹配，过程如下：

• 因为模式串中的字符 A 跟文本串中的头部 4 个字符 “BBC空格” 逐个匹配都失配，所以直接用模式串不断的匹配文本串的下一个，直到模式串中的字符 A 跟文本串的第 5 个字符 A 匹配成功：

  

• 继续往后匹配，模式串的前 6 个字符 ABCDAB 均匹配成功，当模式串最后一个字符 D 跟文本串匹配时失配，显然，下一次匹配时需要用模式串前部的某个字符去跟文本串匹配，但选择模式串前部哪一个字符呢？此时模式串已经匹配的字符数为6个（ABCDAB），然后根据最大长度表可得失配字符 D 前面匹配成功的模式串子串 ABCDAB 的最大相同前缀后缀长度值为 2，所以模式串的前两个字符可以不用比较，直接从模式串第三个字符开始比较。

  

• 模式串从第三个字符 C 开始继续比较，发现 C 再度失配，此时模式串前两个字符 AB 已经匹配成功，模式子串 AB 的最大长度值为 0 ，所以下一次匹配需要从模式串第一个字符开始匹配。

  

• 模式串的第一个字符和空格比较也失配，此时应当去匹配文本串的下一个字符，即从文本串空格的下一个字符 A 开始比较。

  

• 继续比较，模式串前六个字符 ABCDAB 均匹配成功，然后 D 与 C 失配，然后根据最大长度表可得失配字符 D 之前的模式串子串 ABCDAB 对应的长度值为 2，所以模式串的前两个字符 AB 不用比较，根据最大前缀后缀长度我们就可以知道已经和文本串当前字符 C 的前两个字符 AB 匹配，下次直接从模式串第三个字符开始比较。

  

• 接下来的过程匹配成功，整个过程结束。

  

通过上述匹配过程可以看出，问题的关键就是寻找模式串中最大长度的相同前缀和后缀，找到了模式串中每个字符之前的模式子串前缀和后缀公共部分的最大长度后，便可基于此匹配。其实这个最大长度正是next 数组要表达的含义。

3.2 根据最大长度表求 next 数组

根据前面的介绍，字符串 ABCDABD 各个前缀后缀的最大公共元素长度分别为：

模式串	A	B	C	D	A	B	D
最大前缀后缀公共元素长度	0	0	0	0	1	2	0

假设当前字符前面的模式子串最大前缀后缀公共元素长度为 n，那么如果当前字符失配了，下次匹配时模式串用于匹配的那个字符前面就已经有 n 个字符匹配成功了，由此引出了next 数组。

对于给定模式串 ABCDABD，其next 数组如下：

模式串	A	B	C	D	A	B	D
最大前缀后缀公共元素长度	0	0	0	0	1	2	0
next数组	-1	0	0	0	0	1	2

把next 数组跟之前求得的最大长度表对比后，不难发现，next 数组就是最大长度表整体向右移动一位，然后将空出来的首个元素值赋为 -1。也就是某个字符对应的 next 值就是这个字符前面的模式子串的最大长度值。

根据最大长度表求出了next 数组后，当失配时，查找 next 数组确定模式串从哪一个位置开始继续匹配。

3.3 通过递推计算 next 数组

next 数组本质

next[ j ] = k，代表P[ j ] 之前的模式串子串中，有长度为 k 的相同前缀和后缀，即 P₀P₁…P_k-1 = P_j-kP_j-k+1…P_j-1。有了这个next 数组，在KMP匹配中，当模式串中 j 处的字符失配时，下一步用模式串下标为 next[ j ] 的字符继续跟文本串匹配。

递归求解 next 数组

已知next [0, …, j]且next[ j ] = k，如何求出next[j + 1]呢？

情形一：pattern[ k ] == pattern[ j ]

• 若 pattern[ k ] == pattern[ j ]，则next[ j + 1 ] = next[ j ] + 1 = k + 1；

• 实例说明

  如下图所示，假定模式串为 ABCDABCE，已知next[ 0 ]到next[ 6 ]，此处 j 等于 6，且已知next [ j ] = k（P₀P_k-1 = P_j-kP_j-1 = AB，k 为2），因为P_k = P_j = C，使得 P_j+1 之前的模式子串中有前缀 ABC 与后缀 ABC 相同，所以next[ j + 1] = next [ j ] + 1 = k + 1（next[ j + 1] = 3）。

  模式串	A	B	C	D	A	B	C	E
  前后缀相同长度	0	0	0	0	1	2	3	0
  next值	-1	0	0	0	0	1	2	？
  索引	P0	Pk-1	Pk	Pk+1	Pj-k	Pj-1	Pj	Pj+1

情形二：pattern[ k ] != pattern[ j ]

• 若pattern[ k ] != pattern[ j ]，如果此时 pattern[ next[ k ] ] == pattern[ j ]，则 next[ j + 1 ] = next[ k ] + 1

• 如果此时 pattern[ next[ k ] ] != pattern[ j ]，则继续递归 k = next[ k ]，而后重复此过程。 相当于在字符 P_j+1 之前不存在长度为 k+1的前缀 P₀P₁…P_k-1P_k 跟后缀 P_j-kP_j-k+1…P_j-1P_j 相等，那么是否可能存在另一个值 t+1 < k+1，使得长度更小的前缀 P₀P₁…P_t-1P_t 等于长度更小的后缀 P_j-tP_j-t+1…P_j-1P_j 呢？如果存在，那么这个 t + 1 便是next[ j + 1]的值，当于利用已经求得的 next 数组（next[ 0, …, k, …, j ]）进行pattern前缀跟pattern后缀的匹配。

• 解释说明

  为何递归 k = next[k]，就能找到长度更短的相同前缀后缀呢？其实可以这样做，完全是由 next 数组的含义决定的。设 next[ j ]=k，则代表模式串从第一个字符P₀至第 j 个字符 P_j-1，有长度为 k 的相同前缀后缀，即 P₀P₁…P_k-1 = P_j-kP_j-k+1…P_j-1 ，设 next[ k ] = n (n<k)，则代表模式串从第一个字符 P₀ 至第 k 个字符 P_k-1，有长度为 n 的前缀和后缀相匹配，即 P₀P₁…P_n-1 和 P_k-nP_k-n+1…P_k-1 相匹配，而 P_k-nP_k-n+1…P_k-1 是 P₀P₁…P_k-1 的后缀，通过 P_k-nP_k-n+1…P_k-1 这一中间量，我们可以得知 P₀P₁…P_n-1 能够和 P_j-kP_j-k+1…P_j-1中的一个长度为 n 的后缀 P_j-nP_j-n+1…P_j-1相匹配。如果此时 P_k 和 P_j 匹配就可以得到 next[ j + 1 ] = next[ k ] + 1，否则可以重复上述过程。如下图所示：

  

• 实例说明 求得next [ j + 1 ] = 0

  如下表，P_k != P_j 说明 P₀P_k-1P_k ≠ P_j-kP_j-1P_j 。即字符 P_j+1 前的模式子串没有长度为 k+1 的相同前缀后缀，所以应当去寻找长度更短一点的相同前缀后缀。若能在前缀 P₀P_k-1P_k 中不断的递归 k = next[ k ]，找到一个字符P_t 也为 D 使得 P_t = P_j 将会有 P₀P_t-1P_t = P_j-tP_j-1P_j，则最大相同的前缀后缀长度为 t + 1，从而 next [ j + 1] = next [ k ] + 1= t + 1 。若前缀中找不到 D，则代表没有相同的前缀后缀，next [ j + 1] = 0。

模式串	A	B	C	D	A	B	D	E
最大长度表	0	0	0	0	1	2	0	0
next值	-1	0	0	0	0	1	2	？
索引	P0	Pk-1	Pk	Pk+1	Pj-k	Pj-1	Pj	Pj+1

• 实例说明 求得next [ j + 1] 不为0

  给定模式串DABCDABDE，next[ j ] = 3，但 P_j  != P_k，所以不存在长度为 3 + 1 的相同前缀后缀。所以需要寻找长度更短的相同前缀后缀，令 k = next[ k ] = 0，同时 P_k == P_j ，所以 next[ j+1] = k + 1 = 1。

模式串	D	A	B	C	D	A	B	D	E
最大长度表	0	0	0	0	1	2	3	1
next值	-1	0	0	0	0	1	2	3	？
索引	P0	P1	Pk-1	Pk	Pj-k	Pj-2	Pj-1	Pj	Pj+1

代码实现

void getNext(char[] pattern,int next[]) {  
    int pLen = pattern.length;  
    next[0] = -1;  
    int k = -1;
    int j = 0;  
    while (j < pLen - 1) {
//k==-1表示当前模式子串找不到公共前缀后缀，需要从头开始匹配
        if (k == -1 || pattern[j] == pattern[k]) {
//如果此if块是通过k==-1进入的，那么就表明当前pattern[j]位置的模式子串没有找到相同前缀后缀，
//  需要从pattern[j+1]和pattern[0]处开始匹配，所以需要令k++和j++以使得下一轮匹配pattern[j+1]和pattern[0]
//如果次if块是通过pattern[j] == pattern[k]进入的，就表明当前正在匹配的pattern[j]和pattern[k]是能够匹配的，
//  并且匹配成功一个字符就领k++，k的作用有两个：一是记录当前相同前缀匹配到第几个字符了，二是作为当前模式串字符的next值写入到next数组中
            k++;  
            j++;  
            next[j] = k;  
        } else {  
//只有当k != -1 && pattern[j] != pattern[k]时才会进入else，这表明不是从模式串开头找相同前缀匹配失败，
// 而是已经有一定长度的相同前缀之后才发生的匹配失败，这时候不应该从模式串开头寻找前缀，因为在已经遍历过的模式子串中，
// 很可能存在和当前后缀或者更短后缀相同的前缀或更短的前缀，所以令k = next[k]找到这个前缀，然后进入下一轮循环继续匹配
            k = next[k];  
        }  
    }  
} 

3.4 基于next 数组的代码实现

下面，我们来基于 next 数组进行匹配。

模式串	A	B	C	D	A	B	D
next数组	-1	0	0	0	0	1	2

还是给定文本串 “BBC ABCDAB ABCDABCDABDE”，和模式串 “ABCDABD”，现在要拿模式串去跟文本串匹配，如下图所示：

KMP算法流程

• 假设现在文本串 str 匹配到 i 位置，模式串 pattern 匹配到 j 位置
  • 如果 j = -1，或者当前字符匹配成功（即 str[ i ] == pattern[ j ]），都令 i++，j++，继续匹配下一个字符；
  • 如果 j != -1，且当前字符匹配失败（即 str[ i ] != pattern[ j ]），则令 i 不变，j = next[ j ]。即下一次匹配时，模式串从下表为next[ j ]的位置与 str[ i ]继续匹配。

KMP代码

int kmPSearch(char[] str, char[] pattern) {  
    int i = 0;  
    int j = 0;  
    int sLen = str.length;  
    int pLen = pattern.length;  
    while (i < sLen && j < PLen) {    
        if (j == -1 || str[i] == pattern[j]) {  
            i++; j++;  
        } else {       
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

执行过程

• 最开始匹配时，进入while循环
  • j = 0，pattern[ 0 ]跟 str[ 0 ]匹配失败，if (j == -1 || str[i] == pattern[j])条件不成立，所以执行 j = next[ j ]得到 j = -1, i = 0，进入下一轮循环。
  • pattern[ 0 ]跟 str[ 0 ]匹配又失败，但由于 j == -1，if 条件成立使得 i++, j++。得到 i = 1, j = 0
  • pattern[ 0 ]跟 str[ 1 ]失配后，pattern[ 0 ]又跟 str[ 3 ]匹配也失配。此时得到 i = 4, j = 0
• pattern[ 0 ]跟 str[ 4 ]匹配成功，令 i++，j++。得到 i = 5, j = 1

• pattern[ 1 ]跟 str[ 5 ]匹配成功，直到 pattern[ 5 ]跟 str[ 9 ]都匹配成功，直到 pattern[ 6 ]跟 str[ 10 ]匹配失败

• 此时 j = 6, pattern[ 6 ] != str[ 10 ], if (j == -1 || str[i] == pattern[j])条件不成立，执行 j = next[ j ]，得到 j = 2，即模式串从下标为 2 的位置继续匹配

• 此时 j = 2, pattern[ 2 ] != str[ 10 ], if (j == -1 || str[i] == pattern[j])条件不成立，再次执行 j = next[ j ]，得到 j = 0，即模式串从下标为 0 的位置继续匹配

• 此时 j = 0, pattern[ 0 ]与str[ 10 ]再次失配, if (j == -1 || str[i] == pattern[j])条件不成立，再次执行 j = next[ j ]，得到 j = -1，进入下一轮循环 if 条件成立，执行 i++; j++; 使得 j = 0，i = 11，即下一次匹配用pattern[ 0 ] 与 str [11 ]匹配。

  

• 而后模式串与字符串匹配顺利，直到str[ 17 ]字符 C 失配，此时 j = 6，执行 j = next[ j ]，得到 j = 2，继续匹配

• 后续匹配均成功，找到匹配到的子串。

3.5 基于最大长度表与基于next 数组等价

我们已经知道，利用 next 数组进行匹配失配时，模式串下一次开始匹配的位置是对应的 next 值。原因是：

• j 从 0 开始计数，那么当数到失配字符时，j 的数值就是已匹配的字符数；
• 由于 next 数组是由最大长度值表整体向右移动一位得到的，那么失配字符的上一位字符所对应的最大长度值，即为当前失配字符的next 值。

但是next数组的递归求法与使用都不够直观，不如直接使用最大长度表更容易理解KMP算法的思想。

3.6 next 数组的优化

如果用之前递推的方法求模式串 ABAB 的 next 数组，可得其next 数组为{-1, 0, 0, 1}

当它跟文本串 ABACABAB 去匹配的时候，发现 B 跟 C 失配，j = next[ j ] = 1。

让 pattern[ next[ 3 ] ] = pattern[ 1 ] = B 再跟str[ 3 ]匹配时，必然失配。

问题出在 pattern[ j ] 刚好等于 pattern[ next[ j ] ]。当发生失配时，下次 pattern 开始匹配的位置应当是 next [ j ] ，但如果pattern[ j ] = pattern[ next[ j ] ]，必然导致下一次匹配失败，所以不能允许pattern[ j ] = pattern[ next[ j ]]，如果出现 pattern[ j ] = pattern[ next[ j ]]，则需要再次递归，即令 next[ j ] = next[ next[ j ] ]。

下面是优化之后的代码：

void getNextOptimized(char[] pattern, int next[])  {  
    int pLen = pattern.length;  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1) {     
        if (k == -1 || pattern[j] == pattern[k]) {  
            k++;  
            j++;  
            if (pattern[j] != pattern[k]) {
                next[j] = k;
            } else { 
                next[j] = next[k]; 
            }
        } else {  
            k = next[k];  
        }  
    }  
} 

利用优化过后的next 数组求法，可知模式串 ABAB 的 next 数组是{-1, 0, -1, 0}。此时我们面临的新的问题是原始 next 数组是前缀后缀最长公共元素长度值向右移动一位，首位元素赋值为 -1 而得，那么优化后的 next 数组如何快速得到呢。还是以 ABAB 为例，如下表格所示：

模式串	A	B	A	B
索引	P0	P1	P2	P3
最大长度	0	0	1	2
未优化的next数组值	-1	0	0	1
是否需要优化	不需要	next[1] = 0 但 P1 != P0 不需要优化	next[2] = 0 且 P2 = P0 需要优化	next[3] = 1 且 P3 = P1 需要优化
优化后的next值	-1	0	-1	0

对于优化后的next数组可以发现一点：如果模式串的后缀跟前缀相同，那么它们的next值也是相同的，例如模式串 ABCABC，它的前缀后缀都是ABC，其优化后的 next 数组为{-1, 0, 0, -1, 0, 0}，前缀后缀 ABC 的 next 值都为 {-1, 0, 0}。

4 KMP的时间复杂度分析

KMP的算法流程：

• 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
  • 如果 j = -1，或者当前字符匹配成功（即 str[i] == pattern[j]），都令 i++，j++，继续匹配下一个字符；
  • 如果 j != -1，且当前字符匹配失败（即 str[ i ] != pattern[ j ]），则令 i 不变，j = next[ j ]。此举意味着失配时，下一次匹配时模式串从next[ j ]的位置开始匹配。

我们发现如果某个字符匹配成功，模式串首字符的位置保持不动，仅仅是 i++、j++；如果匹配失配，i 不变（即 i 不回溯），模式串会跳过匹配过的 next[ j ]个字符。整个算法最坏的情况是，模式串匹配到了文本串的最后一个字符算法才结束。所以，如果文本串的长度为 n，模式串的长度为 m，那么匹配过程的时间复杂度为 O(n)，算上计算 next 的 O(m)时间，KMP的整体时间复杂度为O(m + n)。