算法 图解 KMP字符串匹配算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
KMP算法解决的问题是：在主字符串M中，寻找子字符串S第一次出现的位置。核心是利用匹配失败后的信息，尽量减少子字符串S与主字符串M的匹配次数以达到快速匹配的目的。具体实现就是通过一个数组来实现，数组本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。

为了让思路更清楚，我们在开始推导之前，先做一些约定

主字符串我们用M来表示，子字符串我们用S来表示，后面简称主串、子串。

现在给到一个主串M=“a b a b c d a b e a b c d a b c d a b d e”，子串S=“a b c d a b d”，要求在主串M中找到子串S出现的第一个位置（下标从 0 开始)，如果不存在，返回-1.

首先最容易想到的是暴力解法，所谓暴力解法就是指将M和S的每一个字符都进行比较，当S从头到尾比较完毕了，都与M的某段字符相等，这时返回对应的下标。

我们先用一些图来辅助理解一下，

如图，刚开始时，主串和子串各有一个指针 i、j

然后 i j 指针开始后移，不停的比较两字符串的值，判断是否相等。如果失配，i j 指针回溯，重新比较。如图，匹配到“a”与"c"两个字符时，失配了

这时，i j 指针回溯，再从主串的第二个元素开始比较

然后发现 b 和 a 不相等，于是指针再回溯，重复这个过程。一直等到字符串匹配上

这时，遍历结束。返回对应下标 13

我们根据图 写出代码

    public int strStr(String haystack, String needle) {
        int m = haystack.length(), s = needle.length();
        int i = 0, j = 0;
        while (i < m && j < s) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j == s) {
            return i - j;
        } else {
            return -1;
        }
    }

显而易见这种暴力的方式，虽然简单，但是好像缺失了一些“灵性”，有没有巧妙一些的解法呢 ？当然是有的，那就是本文要说的 KMP字符串匹配算法 了

在上面的暴力解法中我们看到，遍历过程中，当字符串不匹配时，i j 指针都会回溯，i回溯到i-j+1，j回溯到0，这样其实做了很多无用功，如图

遍历到这个时候，a 与 c 字符不匹配了，那么接下来 i j 指针要回溯

i j 指针会回溯到如下位置

但是我们不难发现，i 指针的回溯做了很多无用功，i指针回溯到了“b”字符，但是从字符“b”开始 继续与子串匹配。还是不匹配的。如果每次失配后，i指针都要回溯的话，无疑增加了很多无用功。KMP就是根据这个思路，在失配时，保持 i 指针不动，然后将 j 指针移动到合适的位置。接下来我们详细探讨一下KMP的推导过程

我们在2.4.1中已经说了，KMP的核心思想就是“在失配时，保持 i 指针不动，然后将 j 指针移动到合适的位置”，那么我们先来看一下，这个所谓“合适的位置”，是什么意思。

主串M=“a b a b c d a b e a b c d a b c d a b d e”，子串S=“a b c d a b d”

还是同样的主串和子串 我们来用一些图来说明一下

图中先按照给定的例子为大家展示一下遍历的过程，暂时不用去管这个“合适的位置”是怎么来的，先跟着走一遍过程，了解KMP的思想。后面我们会为大家展示如何求出这个“合适的位置”

如图，遍历开始，i j 指针的位置都是0

当匹配到 “a” 和 “c” 字符时，失配了

如果按照之前的暴力解法，i指针回溯到i-j+1，j指针回溯到0，然后重新比较。这里我们换一种思路，i 指针不回溯，让 j 指针去到最合适的位置。
我们将j指针回溯到0，继续与主串比较。因为 i 指针就算回溯到 i-j+1 也是无用功，我们索性 i 不动，让j 指针回溯 继续比较。如图

继续往下比较，一直到 字符“e”与"d"失配

此时遵循上边说到的KMP的指针的移动标准，i指针不动,j指针移动到合适位置

为什么图上的位置就是合适的位置呢？ 我们可以观察到，在指针之前，还有a b 两个字符时匹配的。这样我们就可以从子串S的当前位置继续往下匹配，而不需要去管前面的部分了，因为前面已经匹配上了。

如上图，e与c再次失配，那么j指针再次移动位置

“e” 和 “a” 继续失配，因为此时 i 指针 j指针 都在 0 这个位置上，那么 i 指针就不能再不动了，不然就没有任何意义了。所以这里我们继续往后移动指针，i 指针后移一位，j 指针不动。如图

这时、i j 指针的值匹配上了，继续往后移动指针。一直到 " c ” 和 “ d ” 字符 失配

此时 j指针再次移动位置，移动到一个“合适的位置”

如上图，为什么要移动到这个位置呢? 到这里相信大家已经可以看出来了，是因为前面有两个字符“a”、“b”是已经匹配的。

继续往下比较，结果就显而易见了

遍历完毕，返回第一次出现的下标 13。

在2.4.2的推导过程中，我们可以发现，整个KMP的核心就是所谓“合适的位置”到底是什么位置，因为一旦失配，接下来的操作就是将j指针移动到“合适的位置”，再继续往下比较，这就是KMP的核心操作。那么下面我们来具体的看一下，如何求出这个合适的位置。

我们先拿到示例中的子串，观察一下

在上面的遍历演示中，我们可以看出，当j指针在S[6]处失配时，j指针往往会移动到S[2]处。原因就是：S[0]、S[1]位置的字符与S[4]、S[5]位置的字符是一样的，指针从S[6]移动到S[2]后，指针所在位置前面的字符，依然是“ab”，这样我们就可以从指针处继续往下比较，不需要去管指针前面的部分，这样就可以提高效率。

所以我们要求的，就是指针从S[6]跳到S[2]的过程，S[6]之所以能跳到S[2]是因为这两个位置的前面，存在相同的部分，即“ab”，这个是前提

我们先观察该字符串，可以发现，在S[6]处失配时，S[6]之前的部分，是一个包含着相同前后缀的字符串，“a b c d a b ”，包含着一个相同的前后缀“ab”，只有出现这样的结构，才能找到失配处S[6]需要移动到的“合适的位置”，是哪里呢？就是S[2]，为什么呢？因为S[2]前面的字符串是“ab”，与S[6]前边存在相同的部分，指针移动过去之后，指针前面的部分还是“ab”，不需要再比较了。

首先在遍历时，子串的每一个位置，都有可能发生不匹配，那么我们要为子串的每一个位置的字符，都准备一个“合适的位置”，我们可以定义一个next数组，用来存放每个字符失配时，指针将要移动到的那个“合适的位置”，如下

	int[] next = new int[S.length()];

对于字符串“a b c d a b d”，我们先列出他每个子字符串所包含的相同前后缀的最大长度

这个表应该不难理解，例如d对应的是0，那是因为截止到d的字符串“a b c d”，包含0个相同前后缀。第二个b字符，对应的值为2，那是因为截止到b字符的字符串“a b c d a b”，包含了一个最大长度为2的相同前后缀，即“a b”。

从这个表可以得出，当指针在S[n]处失配时，指针要移动到的位置为S[n]前面的字符串（不包含S[n]）中包含的最大的相同前后缀长度。

例如，指针在e处失配了，在它之前的字符串为“a b c d a b”，所包含的最大相同前后缀的长度为2（“a b”），所以指针要移动到下标为2的位置。即“c”，这样指针前边还是“a b”，满足我们上边提出的假设。

基于这个思想 我们可以先得出对于子串S的next数组

    public int[] getNext(String s) {
        int length = s.length();
        int[] next = new int[length];
        for (int i = 1, j = 0; i < length; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

上边的代码中：
1、第5行，J>0说明j指针已经开始后移了，即已经出现和前缀相匹配的后缀了。s.charAt(i) != s.charAt(j)意思是出现了不匹配的元素，此时第6行 j指针回溯。
2、第8行，两指针值相同，说明已经匹配到了相同的前后缀，那两个指针就都++，继续比较下一位。
3、第11行，为next数组填充值。

解题方法如下

    public int strStr(String haystack, String needle) {
        int m = haystack.length(), s = needle.length();
        if (s == 0) {
            return 0;
        }
        int[] next = getNext(needle);
        for (int i = 0, j = 0; i < m; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == s) {
                return i - s + 1;
            }
        }
        return -1;
    }

解题的方法与上面求next数组的方法，思想类似。只不过解题方法中的两个指针是针对于主串和子串。getNext方法中的两个指针针对的都是子串。

第14行做了判断，如果j指针已经等于子串的长度了，说明遍历结束了。就返回子串的第一个元素的下标。即子串在主串中 第一次出现的下标了。

如果还有不太理解的，可以跟着以上代码，自己画图推导一下，很容易就可以理解了。过程还是很清晰的

以上内容，是参考了一下大佬的博客、以及力扣的题解，加上本人的理解得出的。本人初学算法，理解不深，甚至可能某些地方的理解与描述有误。所以如果本文的内容有误，请各位指正

最后、感谢你的阅读