写在前面

以前的数据结构课就学习过KMP算法，但是理解不够深入，一些诸如next数组求法更多是背了然后一笔带过，实际原理没有理解，然后看到这道题虽然想到了KMP，但是就是想不出来怎么写，直接暴力过了，虽然在这道题里KMP算法的时间要比暴力法长，不过，KMP还是更有用一点，所以本文主要详细讲解KMP算法。

题目

分析

题目是字符串匹配，最简单直接的想法就是遍历haystack，对于每一个字符作为起始字符与needle进行比对，出现不匹配的字符就继续遍历下一个字符，直至needle的字符全部匹配返回对应下标，若遍历过后均没有完全匹配，返回-1。这种方法在提交中效率也很高，甚至使用java的substring方法可以到1ms的运行时间，不过本文的重点还是KMP算法，故此法一笔带过不在赘述。

KMP算法

为什么KMP能优化时间复杂度

在暴力法解决问题中，由于对于haystack的每一个字符都要作为首字符与needle进行匹配，所以总的时间复杂度为O(n * m)(n表示haystack的长度，m表示needle的长度)，复杂度比较高的原因就在于对haystack的某个字符作为首字符判断过后，指针需要回溯到该首字符的下一个，而比对中匹配的一部分子串有可能复用，从而可以达到降低时间复杂度的效果。具体可以看下边的两个例子

具体KMP是怎么移动模式串的我们暂不考虑，只是看例子，在示例一中，当字母d和e匹配失败，由于needle中甚至没有字母d，所以可以直接把needle移到当前比对的字符后边，相当于needle的下标归零，haystack的下标向后移一个；在示例二中，字母c和e匹配失败，但是needle的前部还有与haystack相匹配的部分可以利用，所以可以按图中移动，减少比对的次数，相当于将needle的下标回溯到3，将haystack的下标继续向前移动。
通过例子可以发现一个特点，就是遍历haystack的下标可以一直向前移动而不回头(回溯)，这也便是KMP的核心思想：通过辅助的next数组指示needle指针下一次循环需要比对的位置，使得只需要不回头的遍历一次haystack，即可完成字符串的匹配判断。而通过KMP来进行字符串匹配判断只需要提前根据needle获得next数组，然后遍历haystack判断是否匹配，总的时间复杂度遍为O(n + m)(n表示haystack的长度，m表示needle的长度)，大大的节约了时间，也是一个典型的用空间换取时间的例子。
而KMP中最重要的就是如何去定义求解next数组，通过上边的两个示例就能看出对于不同的匹配状态，移动的方法也是不同的，而具体怎么设计移动，我们接下来讨论。

如何设计求解next数组

定义部分

next数组的含义可以很容易明确：当needle的指针匹配到j位置时，发现该位置的字符不匹配，则应该将该指针j回溯到的位置。
其实通过上边的两个例子可以发现一个特点，就是当已经匹配的部分的后缀串与其前缀串相同时，可以将匹配部分与haystack对齐。比如上述示例二，已经匹配的部分为abcab，由于这部分有一个前缀ab和后缀ab相同，所以移动needle时，将这部分相同的地方对齐，也就是将下标j置为2(即相同的前后缀的长度)，而这刚好对应了next数组的定义。既然如此，只要将从0到任意下标位置的前后缀相同的最大长度保存进next数组即可，因为这里存储的数越大，回溯需要判断的字符也就越少，越能提高效率。
到这里我们可以明确一下next数组的定义(我这里直接用的各个前缀后缀的公共元素的最大长度表，只是因为个人认为比较容易理解，大多数的next数组是将这个最大长度表整体向右移动一个元素，并将首元素置为-1来使用)：next[i]表示，needle从下标 0 到 i 的子串，其前缀与后缀串相同的最长的长度。

求解部分

首先考虑初始状态，next[0] = 0，根据定义只有一个字符的时候无法考虑前后缀相同的长度，故初始化为0。
然后考虑后面的值，可以采用双指针，一个i用来遍历模式串needle，另一个j用来表示可能相同的前缀的位置，在初始情况下令i = 1; j = 0;这里求解的过程类似于DP问题的状态转移，可以利用前面求解的结果来计算后面的结果，所以我们通过比较一般的情况来考虑，参考下边的例子。
情况一：

如果i位置的字符与j位置的字符相同，同时将i , j向后移动，且next[i] = next[i - 1] + 1而在遍历的过程中，next[i - 1]的值对应的就是 j 的下标所以可以写成next[i++] = ++j;同时完成移动的过程。
情况二：

根据前边情况一的结论，可以得到图中i, j下标的位置，此时对应的字符c 和 e 不匹配，所以要回溯 j ，但是具体要回溯到哪个位置呢，图中回溯的位置为next[j - 1]，这样是合理的，但是原理呢？
由于此时的i, j下标对应的字符 c 和 e不匹配 也就是目前的最长的相同前后缀串要比5小，只能去考虑更短的长度，也就是要看前缀和后缀还有没有想同的部分。参考下边的图解。

我们希望找到的是图中的 ① 和 ④，不过因为图中绿色填充的部分都已经匹配过了，根据对称性，得到图中的四个部分应该都是相同的，那么我们可以只比较 ① 和 ② ，这两部分相同的前后缀长度也就等同于 ① 和 ④ 两部分的相同的前后缀长度。而 ① 和 ② 这两部分已经在next[j - 1] 计算过了，所以直接使用即可。注意：如果j的下标已经到了0，也就是字符串头的位置，并且j位置的字符与i位置的字符不匹配，那么next[i] = 0 就显而易见了。

求解代码

根据上边的分析，可以得到如下的计算next数组的代码

private int[] next;
private String pattern;

public KMP(String pat) {
        this.pattern = pat;
        if (pattern == null || pattern.length() == 0) {
            return;
        }

        int len = pattern.length();
        this.next = new int[len];
        int i = 1, j = 0;
        while (i < len) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                next[i++] = ++j;

            } else {
                if (j == 0) {
                    next[i++] = 0;
                } else {
                    j = next[j - 1];
                }
            }
        }
    }

由于我是建了一个KMP类，在里边设置了next数组和模式串，所以将next数组的计算过程封装在了KMP的构造器中，封装在函数中也是一样的。

利用next数组实现字符串匹配的判断

有了next数组，进行字符串匹配就很容易了，和计算next数组时有点类似，同样需要两个指针i , j分别表示haystack的下标以及needle的下标，判断时也是两种情况：

i, j 位置的字符相同，将两个指针同时向前移动
i, j 位置的字符不同，保持i下标不动，j 置为 next[j - 1];
思路与上边计算的过程是相同的，就不再过多解释。

public int search(String text) {
        int i = 0, j = 0;
        while (i < text.length() && j < pattern.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
                i++;
            } else {
                if (j == 0) {
                    i++;
                } else
                    j = next[j - 1];
            }
        }
        return j == pattern.length() ? i - j : -1;
    }

完整代码

有了这两部分，对于这道题的完整代码就得到了。

class Solution {

    public int strStr(String haystack, String needle) {
        if(needle == null || "".equals(needle)){
            return 0;
        }
        if(haystack == null || "".equals(haystack)){
            return -1;
        }

        KMP kmp = new KMP(needle);
        return kmp.search(haystack);
    }
}

class KMP {
    private int[] next;
    private String pattern;

    public KMP(String pat) {
        this.pattern = pat;
        if (pattern == null || pattern.length() == 0) {
            return;
        }

        int len = pattern.length();
        this.next = new int[len];
        int i = 1, j = 0;
        while (i < len) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                next[i++] = ++j;

            } else {
                if (j == 0) {
                    next[i++] = 0;
                } else {
                    j = next[j - 1];
                }
            }
        }
    }

    public int search(String text) {
        int i = 0, j = 0;
        while (i < text.length() && j < pattern.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
                i++;
            } else {
                if (j == 0) {
                    i++;
                } else
                    j = next[j - 1];
            }
        }
        return j == pattern.length() ? i - j : -1;
    }
}

虽然代码很长，甚至提交的效率也要比之前的暴力法低，不过在多次使用时KMP的效率还是非常可观的，重新回顾了一遍KMP算法，发现自己当初的理解真的不透，单纯的记忆还是用处不大，还是要理解加复习来巩固才行啊。
如果文章有任何错误还请指出，感恩相遇~

28-实现 strStr()-KMP算法