初识 KMP 算法

朴素算法

在介绍KMP算法之前我们需要先介绍朴素算法。

我们常常会需要进行字符串的匹配，例如在 abababca 这个字符串中找到 ababca 的位置在哪。在传统的朴素匹配算法中，我们需要从两个字符串的头部开始比较，如果相等则匹配第二个字符，直到遇见不相等的字符。以刚才的例子说明：我们将待匹配的字符串，也就是较短的那个叫做子串，被匹配的字符串，也就是较长的那个叫做主串。我们首先比较两个字符串的第1个字符，都是a，继续比较第2个，都是b，直到比较到第4个字符，此时不相等，主串回到第2个字符，子串回到第1个字符。为了方便理解我引入逻辑关系的概念，我们可以将子串看作一个主串上的浮标，可以左右移动，直到匹配时固定。此时两个字符串的逻辑位置关系如下：

主串: abababca
子串:  ababca

此时重新比较第1个字符串，不相等，则主串回到第3个字符，子串回到第1个字符，以此类推直到找到匹配的位置，这便是朴素匹配算法。

// 朴素匹配算法
public int demoAlgorithm(String mainString, String subString) {
    int indexOfMain = 0, indexOfSub = 0;
    while(indexOfMain != mainString.length() && indexOfSub != subString.length()) {
        if (subString.charAt(indexOfSub) == mainString.charAt(indexOfMain)) {
            indexOfMain++;
            indexOfSub++;
        }
        else if (subString.charAt(indexOfSub) != mainString.charAt(indexOfMain) && indexOfSub == 0) {
            indexOfMain++;
        }
        else {
            indexOfMain -= indexOfSub - 1;
            indexOfSub = 0;
        }
    }
    return indexOfMain - indexOfSub;
}

不回溯的KMP算法

我们还是以在 abababca 这个字符串中找到 ababca 的位置为例，当主串与子串比较到第5位不相同时，我们已经知道朴素算法的做法。但是我们可以很容易看出子串第3、4位和第1、2位是相等的，也就是说，目前比较到第5位不同，但是前4位主串与子串是相通的，又因为第3、4位与第1、2位相同，所以我们可以将子串回溯到第3位，让第3位继续与主串的第5位进行对比，主串3、4位之前与子串3、4位相匹配，此时也一定会与子串1、2位匹配。

主串: abababca
子串:   ababca

KMP算法的核心就是主串不回溯，而要达到这个目的，我们需要引出next数组的概念。

以 ababca 子串为例，我们知道第1、2位与3、4位相同，所以可以在第5位失配的时候直接回溯到第3位而非第1位。而 next 数组的目的就是告诉程序当子串失配回溯时应该回溯到什么位置。还是以 ababcd 为例，第5位失配时，我们已经知道要回溯到第3位，而如果第4位失配，应该回到什么位置呢？我们此时换一个主串来看看情况。

主串：abaababca
子串：ababca

第4位失配，观察到子串第3位与第1位匹配，我们可以直接将子串回溯到第2位，让第2位继续与主串的第4位进行对比

主串：abaababca
子串：  ababca

那么此时 next 数组的计算方式已经跃然于纸了，便是计算出当前位之前的串相匹配的前缀与后缀中，最长的字符串的长度。换句话说，我们用子串与子串自己来匹配。下面给出计算 next 数组的代码，由于学艺不精，拆成了三个函数写，第一个函数计算 next 数组，第二个函数计算最长的相匹配的前后缀，第三个函数检测当前的前后缀是否匹配。

void calculateNext() {
    next = new int[subStr.length()];
    for (int i = 1; i < subStr.length(); i++){
        next[i] = findBiggestPairFrontAndEnd(i) + 1;
    }
}

int findBiggestPairFrontAndEnd(int end) {
    int maxLength = 0;
    for (int i = 1; i < end; i++) {
        if (isFrontAndEndPair(i,end)) {
            maxLength = i;
        }
    }
    return maxLength;
}

boolean isFrontAndEndPair(int length, int end) {
    for (int i = 0; i < length; i++) {
        if (subStr.charAt(i) != subStr.charAt(end - length + i)) {
            return false;
        }
    }
    return true;
}

下面我们探讨一种情况，先令子串为 aaaab ，根据上面的方法，可以算出它的 next 数组为 01234 ，观察下面的情况：

主串：aaabaaaab
子串：aaaab

当前第4位失配，根据 next 数组，应该回溯到第3位，也就是下面这样，此时依然不匹配。根据 next 数组，回溯到第2位，还是不匹配，最终需要回溯到第0位，也就是从头开始。那我们需要对 next 数组作出改进，防止这种反复回溯的情况发生影响匹配效率。

主串：aaabaaaab
子串： aaaab

我们继续改进 next 数组，计算它的修正值。观察可以发现，每次回溯后如果需要继续回溯，那么 next 值修改为其回溯位的 next 值，便实现了直接回溯到位的目的，下面是计算修正值的函数。

void calculateNextValue() {
    calculateNext();
    nextValue = new int[subStr.length()];
    for (int i = 0; i < subStr.length(); i++){
        if (i <= 1) {
            nextValue[i] = next[i];
        }
        else if (subStr.charAt(next[i] - 1) == subStr.charAt(i)) {
            nextValue[i] = nextValue[next[i] - 1];
        }
        else {
            nextValue[i] = next[i];
        }
    }
}

现在我们便可以使用修正过的 next 函数去匹配主串，每当失配时，子串回溯到失配位对应的 next 值位上去，匹配代码如下：

public int indexOf(String mainString, String subString) {
    subStr = subString;
    mainStr = mainString;
    int indexOfMain = 0, indexOfSub = 0;
    calculateNextValue();
    while(indexOfMain != mainStr.length()) {
        if (subStr.charAt(indexOfSub) == mainStr.charAt(indexOfMain)) {
            indexOfMain++;
            indexOfSub++;
        }
        else if (subStr.charAt(indexOfSub) != mainStr.charAt(indexOfMain) && indexOfSub == 0) {
            indexOfMain++;
        }
        else {
            indexOfSub = nextValue[indexOfSub] == 0 ? 0 : nextValue[indexOfSub] - 1;
        }
        if (indexOfSub == subStr.length()) {
            break;
        }
    }
    return indexOfMain == mainStr.length() && indexOfSub == 0 ? -1 : indexOfMain - indexOfSub;
}

这就是KMP算法的简要介绍。