子字符串查找（2）——KMP算法

作者: null12 | 来源:发表于2018-03-22 17:47 被阅读0次

KMP算法文章合集
算法（2）KMP算法
子字符串查找（1）
JavaScript 二分查找 & KMP 算法
KMP算法
iOS-字符串查找
子字符串查找（2）——KMP算法
KMP算法——寻找子串位置
分享几道常见字符串算法题
KMP

一、定义

KMP(Knuth-Morris-Pratt)算法，其实是对暴力查找算法的优化。
在暴力查找算法中，用于追踪文本的指针i每次都会回退到起始位置+1。事实上，当出现不匹配时，就能知晓一部分文本内容信息（模式字符串中当前匹配失败的字符前的所有字符）。

KMP算法在匹配失败时，总是将模式指针j设置为某个值以使文本指针i不用回退，所以关键是如何重置指针j的值，而这只与模式字符串本身有关，需要对模式字符串进行预处理，计算每个字串的最大公共前后缀长度。

3-1 暴力查找算法与 KMP算法的对比

二、基本思想

2.1 KMP匹配示例

以模式字符串“ABCDABD”、文本“BBC ABCDAB ABCDABCDABDE”为例：

首先，文本“BBC ABCDAB ABCDABCDABDE”的第一个字符与模式字符串"ABCDABD"的第一个字符，进行比较。
因为B与A不匹配，所以模式字符串后移1位，直到模式字符串有一个字符，与文本的第一个字符相同为止。

接着比较模式字符串和文本的下一个字符，还是相同。那么，继续后移，直到模式字符串中有一个字符与文本中对应的字符不相同为止。

当空格与D不匹配时，其实已经知道文本的前面6个匹配字符是"ABCDAB"。KMP算法的思想就是，设法利用这个已知信息，不要把"搜索位置i"移回已经比较过的位置，而是继续把它向后移，这样就提高了效率。
那么如何做到这一点呢？可以针对模式字符串，算出一张《部分匹配表》（Partial Match Table），如下图（如何计算后面讲解）：

按照下面的公式算出模式字符串向后移动的位数：
模式字符串的右移位数 = 已匹配的字符数 - 最后匹配字符的部分匹配值

上述图中，空格与D不匹配，模式字符串还要继续往后移。这时，“已匹配的字符数”=6（"ABCDAB"），“最后匹配字符的部分匹配值”B=2。所以，移动位数 = 6 - 2 = 4，于是将模式字符串后移4位。

此时，空格与Ｃ不匹配，模式字符串还要继续往后移。这时，“已匹配的字符数”=2（"AB"），“最后匹配字符的部分匹配值”B=0。所以，移动位数 = 2 - 0 = 2，于是将模式字符串后移2位。

此时，空格与A不匹配，直接后移1位。

此时，C与D不匹配，模式字符串还要继续往后移。这时，“已匹配的字符数”=6（"ABCDAB"），“最后匹配字符的部分匹配值”B=2。所以，移动位数 = 6 - 2 = 4，于是将模式字符串后移4位。

逐位比较，直到模式字符串的最后一位，发现完全匹配，于是搜索完成。注：如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，重复上述步骤即可。

2.2 构造部分匹配表

上述示例中用到了一张部分匹配表（Partial Match Table）。那么如何构造呢？先来看两个概念：前缀和后缀。
前缀：指除了最后一个字符以外，一个字符串的全部头部组合。
后缀：指除了第一个字符以外，一个字符串的全部尾部组合。

例如，对于字符串“ABCDABD”：
前缀：A、AB、ABC、ABCD、ABCDA、ABCDAB
后缀：BCDABD、CDABD、DABD、ABD、BD、D

2.3 部分匹配表的本质

对于部分匹配表，所谓“部分匹配值”就是“前缀”和“后缀”的最长共有元素的长度。

以“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

再比如，"ABCDAB"之中有两个"AB"，那么它的“部分匹配值”就是2（"AB"的长度）。
模式字符串移动的时候，第一个"AB"向后移动4位（已匹配字符串长度6-已匹配字符串的最大公共前后缀2），就可以来到第二个"AB"的位置，如下图：

实际上，当出现失配时，并不需要真的去移动模式字符串。
上图中，失配位置j=6，移动后重新比较的位置j=2，我们可以发现j=2就是已匹配字符串“ABCDAB”的最大公共前后缀长度。
所以，可以专门用一个next[j]数组保存每个字符的回溯位置，有如下映射关系：

索引j	0	1	2	3	4	5	6
搜索词	A	B	C	D	A	B	D
部分匹配值	0	0	0	0	1	2	0
`next[j]`	-1	0	0	0	0	1	2

注：可以观察到 next 序列其实就是部分匹配值整体右移1位，next[0]记 -1，next[1]记 0

其本质就是一个确定有限状态机（DFA）：

2.4 构造next[]数组

假设模式字符串为P₀P₁P₂…P_n ，用一个next[]数组记录模式字符串的部分匹配映射值。
next[j]=k表示：子串P[0~j-1]的最大公共前后缀长度为k。
初始时，记next[0]=-1，next[1]=0，且假设已知next[j]=k。则转化为一个数学归纳问题：
①初始：next[0]=-1，next[1]=0
②已知：next[j]=k
③求解next[j+1]

求解过程：
next[j]=k说明P[0]～P[k-1]与 P[j-k]~P[j-1]依次相同。

如果P[k] = P[j]，那么next[j+1] = k+1，即子串P[0]～P[j]的最大公共前后缀长度为k+1。
如果P[k] ≠ P[j]，那么需要将P[0]~P[k]右移（参见2.3 部分匹配表的本质），右移多少位呢？
令j'=next[k]（next[k]表示子串P[0]～P[k-1]的最大公共前后缀长度），j'即右移位数。然后重复上述步骤，继续比较`P[j']=P[j]。

2.5 构造next[]数组的实现源码

构造 next[]数组：

/**
 * 根据模式字符串，生成next数组
 */
public int[] makeNext(String ptn) {
    if (ptn == null)
        throw new IllegalArgumentException("ptn");
 
    int n = ptn.length();
    int[] next = new int[n];
 
    next[0] = -1;
    int j = 0; // 指针j跟踪当前待求解的模式字符
    int k = next[j]; // 假设已知next[j]==k
 
    while (j < n - 1)// 模式字符串的next[0]已知，故剩余n-1个待求解字符
    {
        if (k == -1 || ptn.charAt(j) == ptn.charAt(k)) {
            next[j + 1] = k + 1;
            k++;
            j++;
        } else {
            k = next[k];
        }
    }
    return next;
}

三、KMP算法实现

public int KMP(String ptn, String txt) {
    int[] next = makeNext(ptn);
 
    int i = 0, j = 0;         // i指示文本，j指示模式字符串
    while (i < txt.length() && j < ptn.length()) {
        if (next[j] == -1 || ptn.charAt(j) == txt.charAt(i)) {
            i++;
            j++;
        } else {
            j = next[j];    // 模式字符串右移
        }
    }
    if (j == ptn.length())    // 匹配成功
        return i - j;
    else                      // 匹配失败
        return -1;
}