KMP算法的个人理解

KMP算法求解的是什么问题？

字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置。例如如下两个字串：

String a = "bacbababadababacambabacaddababacasdsd";

String b="ababaca"

KMP算法为什么快？

首先，我们采用一般的算法求解匹配字符串的问题，假设目标字串为"abcdcabccdacb"，长度为n，要匹配字串为“cab”，长度为m，那么一般算法会如何求解？那就是将子串与主串从主串第一位开始匹配，进行一对一匹配，当遇到不匹配的字符时，向前移动一位，也就是从目标字串的第二位开始一对一匹配，直到目标字串的末尾（实际比较时，下标移动到n-m）。这样时间复杂度是(n*m)

KMP算法可实现时间复杂度是（n+m）为何简化了时间复杂度：

充分利用了目标字符串ptr的性质（比如里面部分字符串的重复性，即使不存在重复字段，在比较时，实现最大的移动量）。

   普通算法的实现：

/**
 * 字符串匹配的普通算法：在目标字串中找到与匹配字串相等的字串，若找到
 * 返回目标字串匹配的小标，否则，返回-1
 */
public class NormalMatching {
    public int match(String targetStr, String matchStr) {
        for (int i = 0; i < targetStr.length()-matchStr.length()+1; i++) {
            for (int j = 0; j < matchStr.length(); j++) {
                char targetChar = targetStr.charAt(i + j);
                char matchChar = matchStr.charAt(j);
                if (matchChar != targetChar) {
                    //如果发现不匹配，没必要接着内循环了，跳出内循环，外循环将targetStr+1进入内循环再匹配
                    break;
                } else {
                    //如果字符匹配，判断j是否等于matchStr-1，若相等，
                    //则说明内循环结束，字符均匹配，return true，否则接着内循环匹配
                    if (j == matchStr.length() - 1) {
                        return i;
                    } else {
                        //
                        continue;
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String targetStr = "absdfcab";
        String matchStr = "cab";
        NormalMatching matching = new NormalMatching();
        System.out.println(matching.match(targetStr, matchStr));
    }
}

这里不想使用标记位，语句控制复杂了一些。

接下来，我们学习使用KMP算法来所解决字符串匹配问题

预备知识

了解了KMP算法的含义是求解字符串问题，那么我们就先算法中需要用到的字符串概念做一个学习。

前缀与后缀

所谓前缀，其实一个字符串的子串，那这个子串有什么特点呢，那就是一定包含第一个字符并不包含最后一个字符，我们举一个例子：

String s = "ABCDABD"

那么他的前缀就有：A AB ABC ABCD ABCDA ABCDAB

以此类推，后缀的概念就很好理解了，那就是：一定包含最后一个字符并不包含第一个字符，对于 s来说，他的后缀就有：BCDABD CDABD DABD ABD BD D

      部分匹配值

这里，我们需要解释一下部分匹配值这个概念，也许在其他文章中会叫其他名字或根本没有这个概念，这里所有的概念都是为了讲解KMP算法，只要我们通过这些概念理解了KMP,那么这些概念叫什么甚至有没有都也无所谓了。

"部分匹配值"就是"前缀"和"后缀"的交集中，长度最大的那个。以s = "ABADABA"为例，它的前缀有A AB ABA ABAD ABADA ABADAB 后缀有BADABA ADABA DABA ABA BA A；那么，它的前缀和后缀中的交集有A ABA，那么它的部分匹配值就是ABA

next[]数组

    其实，理解KMP算法的难点之一，就是理解next数组，KMP算法就是用next数组来提高匹配速度的，下面，我们就讲解一下next数组

    next数组其实就是，一个字串所有子串的部分匹配值的数组，而这个字串，必须包含第一个字符。这个说法很拗口，看例子：

以"ABCDABD"为例，它的包含第一个字符的子串有：

－"A"的前缀和后缀都为空集，共有元素的长度为0；

－"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

－"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

－"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

－"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

－"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

－"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。如下：

     

    

    KMP算法实质

    KMP算法的实质，就是利用部分匹配值，来减少普通循环的次数，提高效率。

举一个例子，匹配字符 matchStr = "ABDAB"，目标字符为“ABCABDBCBABDABC”

matchStr的部分匹配值是AB，我们设L = "AB"，其他字符用x c y 代替

targetStr :LxxxLcccxc

matchStr:LxxxLyy

当目标字符和匹配字符的L匹配时，我们就不需要再仅仅向前移动一位来匹配，如下：

LxxxLcccxc

LxxxLyy

而是将匹配字串向前移动到目标字串的第二个L处进行比对，如下：

LxxxLcccxc

LxxxLyy

那么，目标字串的第二个L的下标是多少呢？也就是说我们往前移动多少呢？答案就藏在next数组中：当对比到不相等的字符时，向前移动最后一个匹配的字符的next数组中对应值+1，不多说，看例子：

targetStr: ABDABBCDABCDABDABC

matchStr:ABDABC

A B D A B C

matchStr next[] = [0,0,0,1,2,0]

第一次匹配时，不匹配的字符为C，如下：

ABDABBCDABCDABDABC

ABDABC

那么最后一个匹配的字符是B，它对应的next数组中的值为2，那么，我们下标就向前移动三步，从0变成3，如下

下标： 0 1 2 3 4 5 6 7......

targetStr： A B D A B B C D A B C D A B D A B C

matchStr： A B D A B C

这样就一下子移动了3下，相比普通方法的一步步向前移动，效率大了很多。了解到这，我们可以开始编码了：

       我把整个逻辑做了拆分，如下：

1、计算Next数组；

1.1、计算一个字串的匹配值

1.2、为matchStr计算匹配值列表，也就是next数组

2、进行匹配

代码如下：

计算一个字串的匹配值：

  /**
     * 计算匹配值
     * A return 0； AB return 0； AA return 1；ABA return 1；ABDAB return 2
     * @param str
     * @return
     */
    private int calculateMatchValue(String str) {
        if (str == null || str.length() == 0 || str.length() == 1) {
            return 0;
        }
        if (str.length() == 2) {
            if (str.charAt(0) == str.charAt(1)) {
                return 1;
            }
            return 0;
        }
        int orginalStrLength = str.length();

         //长度递减的取前缀和后缀做比较，若相等直接返回长度
        for (int i = orginalStrLength - 1; i >= 0; i--) {
            String preStr = str.substring(0, i);
            String sufStr = str.substring(orginalStrLength - i, orginalStrLength);
            if (preStr.equals(sufStr)) {
                return preStr.length();
            }
        }
        return 0;
    }

计算next数组：

//计算Next数组
    private void calculateNextArr() {
        if (matchStr == null && matchStr.length() == 0) {
            return;
        }
        next = new int[matchStr.length()];
        for (int i = 0; i < matchStr.length(); i++) {
            String subString = matchStr.substring(0, i + 1);
            next[i] = calculateMatchValue(subString);
        }
    }

    //debug
    public void debugNextArr(){
        calculateNextArr();
        System.out.println("next arr:"+ Arrays.toString(next));
    }

匹配：

public int match() {
        if (targetStr == null || targetStr.length() == 0) {
            return -1;
        }
        if (matchStr == null || matchStr.length() == 0) {
            return -1;
        }
        int targetStrLength = targetStr.length();
        int matchStrLength = matchStr.length();
        calculateNextArr();
        int i = 0;
        while (i <= targetStrLength - matchStrLength + 1) {
            for (int j = 0; j < matchStrLength; j++) {
                char targetChar = targetStr.charAt(i + j);
                char matchChar = matchStr.charAt(j);
                if (matchChar != targetChar) {
                    //若不相等，则向前移动next[j]+1个位置
                    i = i + next[j] + 1;
                    break;
                } else {
                    //如果字符匹配，判断j是否等于matchStr-1，若相等，
                    //则说明内循环结束，字符均匹配，return true，否则接着内循环匹配
                    if (j == matchStr.length() - 1) {
                        return i;
                    } else {
                        continue;
                    }
                }
            }
        }
        return -1;
    }

测试：

public static void main(String[] args) {
        KMPMatching kmpMatching = new KMPMatching();
        kmpMatching.setTargetStr("ABCCACDAFVDABCAB");
        kmpMatching.setMatchStr("ABCA");
        kmpMatching.debugNextArr();
        System.out.printf("result:"+kmpMatching.match());
    }