1. 理解过程

从原串s[i]中找到是否有匹配模板串p[i]的，有的话返回开始匹配的的位置

• 暴力算法怎么做

int search(String pat, String txt) {
    int M = pat.length;
    int N = txt.length;
    for (int i = 0; i <= N - M; i++) {
        int j;
        for (j = 0; j < M; j++) {
            if (pat[j] != txt[i+j])
                break;
        }
        // pat 全都匹配了
        if (j == M) return i;
    }
    // txt 中不存在 pat 子串
    return -1;
}

• 如何去优化

假设在i-1的时候都是匹配的，到第i个的时候不匹配。每一趟匹配过程中出现的字符不相等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式串向右滑动到尽可能远的一段距离后，继续进行比较。

2. 思想

最大后缀等于前缀next[i]，用来让j回溯

next[i] = j表示为 p[1, j]= p[i - j + 1, i]

应用：利用已经得到的“部分匹配”的结果的后缀等于模式串的前缀，让模式串向右滑动到一段距离后继续匹配（让模式串向后移动就是j指针回溯）

求next数组：

实现