算法解决问题：指定原字符串s与模式串p，需要找到p在s中第一次出现的位置。也就是Java中的s.indexOf(p)

常规做法，逐一匹配。最优时间复杂度为，最坏时间复杂度为。

    public int indexOf(String s, String p) {
        if (p.length() == 0) return 0;
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int size = ss.length - pp.length;
        for (int i = 0; i <= size; i++) {
            boolean match = true;
            for (int j = 0; j < pp.length; j++) {
                if (ss[i + j] != pp[j]) {
                    match = false;
                    break;
                }
            }
            if (match) return i;
        }
        return -1;
    }

那么，有没有一种时间复杂度稳定的算法呢？

KMP算法

KMP算法是在字符串s中找出模式串p，并且时间复杂度为的算法。

一、前缀和后缀

什么是前缀、后缀？字符串以啥开头，前缀就是啥；以啥结尾，后缀就是啥，但二者都不包括其自身。
以abacaba为例：
前缀有a、ab、aba、abac、abaca、abacab；
后缀有a、ba、aba、caba、acaba、bacaba。

二、pmt表（Partial Match Table）

pmt表是kmp算法的核心。
什么是pmt表？
pmt表用一个数组表示，数组的长度等于模式串p的长度。其中pmt[i]代表p[0 : i]中，前缀与后缀重叠的最大长度。

举例，p = "abcabxabcab"
当i = 4时：p[0 : i]为"abcab"，其前缀与后缀最大重叠为"ab"，故pmt[4] = 2。
当i = 5时：p[0 : i]为"abcabx"，其前缀与后缀最大重叠为""，故pmt[5] = 0。

以此类推，对于p = "abcabxabcab"，pmt表如下：

p	a	b	c	a	b	x	a	b	c	a	b
pmt	0	0	0	1	2	0	1	2	3	4	5

pmt表的意义

pmt表有什么意义呢？

在常规做法中，即使s[u : u + i - 1]与p[0 : i - 1]匹配成功，但是s[i] != p[i]，那么就会回溯到s[u + 1]与p[0]作比较。
相当于p是一个窗口，每次移动一格，然后从头开始比较，直到某项匹配失败，然后再移动一格，接着从头匹配。

逐一匹配

这么做的问题在于完全舍弃了之前的匹配结果。

在kmp算法中，同样以p为窗口在s中进行匹配。当在第i项失配时，只需要将窗口右移使得前缀与之前的后缀重叠，就可以继续匹配了。而这个移动的距离正是通过pmt表来得到。
这样一来，就不用每次都从头匹配了，因为前面的项是已经进行过匹配的了。

通过pmt移动窗口
通过pmt移动窗口

这个算法的思想理解起来其实挺容易的，但是它看起来很难理解的原因是很难用文字去表述出来。如果有动图或者游标卡尺之类的小道具的话就很好理解了。
当然了，最难的还是发明轮子，而不是造轮子，也不是理解轮子怎么造。

三、使用代码实现

理解了思路之后，代码实现就是顺水推舟了。

首先创建pmt表：

    // 双指针计算pmt数组
    int[] pmt(char[] p) {
        int[] pmt = new int[p.length];
        pmt[0] = 0;
        // 双指针，i在j右边
        for (int i = 1, j = 0; i < p.length; ) {
            if (j == 0 && p[i] != p[j]) {
                pmt[i] = 0;
                i++;
            } else if (p[i] == p[j]) {
                pmt[i] = j + 1;
                i++;
                j++;
            } else { // p[i]!= p[j] && j!= 0
                // 在i、j处失配，但是之前的都是匹配的
                j = pmt[j - 1];
            }
        }
        return pmt;
    }

通过pmt表，我们可以得知失配时应该怎么移动窗口。不用证明可以得到，当p[i]失配时，接下来的匹配项是p[pmt[i - 1]]。
然后使用双指针进行匹配：

    int kmp(String s, String p) {
        int[] pmt = pmt(p.toCharArray());

        // s指针
        int i = 0 /* s指针 */, j = 0 /* p指针 */; // 双指针
        while (i < s.length() && j < p.length()) {
            if (s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else if (j == 0) { // p[0] 匹配不上，那么s指针右移一位
                i++;
            } else { // p 右移
                j = pmt[j - 1];
            }
        }
        return j == p.length() ? i - j : -1;
    }

难点
这里有一个难点，在求pmt数组的过程中，有这么一句：

            } else { // p[i]!= p[j] && j!= 0
                j = pmt[j - 1];
            }

即，当p[i]与p[j]不匹配，并且j != 0（即：i - 1 与 j - 1 及之前的项是匹配成功的！）时，j = pmt[j - 1]。为什么要这么赋值？
如图，当i、j失配时，很明显，需要把j指针移动到j'处继续匹配。

失配

对于j指针来说，这里的'c'匹配失败，所以需要把j往左移动。但是应该移动到什么位置呢？如之前第二节中所言，那不就应该移动到前缀与后缀重叠的位置吗！

移动 j 指针，使前后缀重叠

注意到pmt数组的意义正是前后缀重叠的最大长度，也就是说j' = pmt[j - 1]

网上说kmp算法很难理解，的确如此。而它的核心难点就是求pmt表的这段代码。只要理解了这点，整个kmp算法也就迎刃而解了。其实整个kmp算法围绕着两件事进行：前后缀与移动窗口。如果真的理解不了，背下来就行，就像背公式一样，开始的时候不一定理解，到后来学的深入了就会茅塞顿开。

完整代码（这里的next表完全可以直接用pmt表代替）

    int kmp(String s, String p) {
        int[] next = next(p.toCharArray());

        // s指针
        int i = 0 /* s指针 */, j = 0 /* p指针 */; // 双指针
        while (i < s.length() && j < p.length()) {
            if (s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else if (j == 0) { // p[0] 匹配不上，那么s指针右移一位
                i++;
            } else { // p 右移
                j = next[j];
            }
        }
        return j == p.length() ? i - j : -1;
    }

    int[] next(char[] p) {
        int[] next = pmt(p);
        System.out.println("p: " + Arrays.toString(p));
        System.out.println("pmt: " + Arrays.toString(next));
        if (next.length > 0) System.arraycopy(next, 0, next, 1, next.length - 1);
        next[0] = 0;
        return next;
    }

    // 双指针计算pmt数组
    int[] pmt(char[] p) {
        int[] pmt = new int[p.length];
        pmt[0] = 0;
        // 双指针，i在j右边
        for (int i = 1, j = 0; i < p.length; ) {
            if (j == 0 && p[i] != p[j]) {
                pmt[i] = 0;
                i++;
            } else if (p[i] == p[j]) {
                pmt[i] = j + 1;
                i++;
                j++;
            } else { // p[i]!= p[j] && j!= 0
                // 在i、j处失配，但是之前的都是匹配的
                j = pmt[j - 1];
            }
        }
        return pmt;
    }