字符串匹配3：KMP算法

KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。

与BM算法类似，KMP算法的思想也是在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。

KMP从前向后逐字匹配，不匹配的字符我们称为坏字符，坏字符之前已匹配的子串我们称为好前缀。

[1221221243453425]
[122124]
      ↑ bad word

KMP的思路是，对好前缀找出一种规律，使得滑动距离变大。那么算法核心就变成了找到这么一种规律。
和BM算法类似，我们实际上是寻找到和好前缀的后缀子串相匹配的好前缀的前缀子串，然后滑动将他们对齐，如上面的好前缀12312,其后缀12 和 2 在好前缀中都有字串可以对齐。我们把这种相匹配的好前缀的前缀子串称为可匹配前缀子串，把向匹配的好前缀的后缀子串称为可匹配后缀子串，而在众多可匹配串之中我们只需要关注最长的那个，在这里就是12这被称为最长可匹配后缀子串和最长匹配前缀子串。

假设坏字符在模式串对应的位置是 i ，最长可匹配子串的的最后一个字符的位置是j则对齐需要滑动的长度skip可以通过如下计算得到

skip = i - (j+1)
// j+i 就是最长可匹配子串长度

和BM算法一样，我们可以通过预处理模式串得到每个好前缀的最大可匹配子串的长度，从而计算出滑动距离skip，然后将其做成next数组直接使用。这个next数组也被称为失效函数（failure Function）

失效函数

通过预处理模式串，得到每个好前缀的最长可匹配前缀子串的最后一个字符的位置做成失效函数加速匹配过程。

next数组（失效函数）的处理思路是：对于好前缀n[0,k] ，假设前一个好前缀n[0,k-1]的最大可匹配前缀子串的末尾index是i

如果n[k] == n[i+1]，那么next[k] = i+1
n[k] != n[i+1],由于我们已经确定n[0,k-1]的最长可匹配前缀可以转换和后缀是一致的，而n[0,k]相当于在此这个前缀的基础上多了一个n[k],于是我们可以将问题转换成这这个最长可匹配前缀n[0,m]拼上n[k]组成的新的好前缀[n[0,m],n[k]]（其实就是最长可匹配后缀接上新的字符）的失效函数计算问题
依此类推我们可以通过最初元素为只有一个时的好前缀处理，向后一直处理到长度为k的好前缀，知道完成构建失效函数

实现

kmp算法实现的核心是next数组的构建。需要明确的是next数组的index是坏字符的index-1，也就是好前缀的end index，其值是最大可匹配前缀的end index。这样清晰的定义可以方便我们实现。

package cn.lishiyuan.algorithm.strings;  
  
/**  
 * KMP算法  
 */  
public class KMPMatcher implements Matcher{  
  
    @Override  
    public boolean match(CharSequence source, CharSequence word) {  
        return find(source,word) != -1;  
    }  
  
    @Override  
    public int find(CharSequence source, CharSequence word) {  
        // codePoints或者chars  
        int[] sourceArray = source.chars().toArray();  
        int[] wordsArray = word.chars().toArray();  
  
        if (sourceArray.length < wordsArray.length){  
            return -1;  
        }  
  
        if (wordsArray.length == 0){  
            return -1;  
        }  
  
        int[] next = failureFunction(wordsArray);  
  
        int index = -1;  
  
        int i = 0;  
        int j = 0;  
  
        while (i < sourceArray.length){  
            if(sourceArray[i] == wordsArray[j]){  
                // 向后匹配看看是否还相同  
                i++;  
                j++;  
            }else if(j > 0){  
                // 非第一个字符就失败  
                // 坏字符之前的好前缀的末尾index  
                int goodPrefixEnd = j - 1;  
                // 对齐， j 就是下个字符的位置  
                j = next[goodPrefixEnd] + 1;  
            }else {  
                // 第一个字符就失败则主串向后  
                i++;  
            }  
  
            // // 已经到最后一位了，找到了，因为必然是从第一个if过来的在j++后必然超出的word的最大index  
            if(j == wordsArray.length){  
                // abac ac , 这里也就是 i = 4 j=2；因为必然是从j++和i++过来的  
                index = i - j;  
                break;            }  
        }  
  
        return index;  
    }  
  
    private int[] failureFunction(int[] words){  
        // next数组 index是好前缀的最后index，值是最长可匹配前缀子串的最后index  
        int[] next = new int[words.length];  
        next[0] = -1;  
        // 上个长度的最长可匹配前缀子串的最后index  
        int maxIndex = -1;  
  
        for (int i = 1; i < words.length; i++){  
            if (words[i] == words[maxIndex+1]){  
                // 当前长度的末尾字符等于上个长度的next的下个字符则直接在其基础上加一  
                maxIndex ++;  
            }else {  
                // 如果不相等，则需要缩小前缀规模查找  
                // words[i] != words[maxIndex+1]表示下个字符与该规模的前缀子串不相同，需要进一步缩小  
                // maxIndex != -1 没有可匹配子串
                while (maxIndex != -1 && words[i] != words[maxIndex+1]){  
                    // 此时我们已经确定i-1 到 0 的最长可匹配后缀等于最长可匹配前缀也就是 0 到 maxIndex                    // 那么我们需要将这个最长可匹配前缀当作好前缀来处理  
                    /**  
                     * 比如 当前好前缀是 [123457123456]  
                     * 我们已经确定 [12345712345]的最长可匹配前缀是[12345]，我们当前的情况是在此前缀上多了一个6  
                     * 这就可以将问题转换成好前缀是[123456]的情况，  
                     * 而好前缀是[12345]的情况我们是知道的，所以我们将maxIndex变成前一个好前缀的最长可匹配前缀的endIndex  
                     */                    maxIndex= next[maxIndex];  
                }  
  
                // 如果找到了则加一  
                if(words[i] == words[maxIndex+1]){  
                    maxIndex ++;  
                }  
  
            }  
  
            next[i] = maxIndex;  
        }  
  
        return next;  
    }  
  
}

设主串的长度是n，模式串的长度是m

空间复杂度
使用了next数组，空间复杂度是O(m)

时间复杂度
kmp算法在模式匹配遍历过程中是不会倒退的，需要的时间为n，在构建next数组时需要的时间时m，总的时间复杂度时O(n+m)

失效函数

实现

评论已关闭

最新文章

分类