题目: 实现 strStr()

分析

字符串匹配最简单的思路是暴力破解法。

暴力破解是指循环字符串的每个位置，比较该位置开始的长度为匹配串长度的字符子串是否和匹配串可以完全匹配。

暴力破解法有两层循环，

因为需要循环字符串的每个位置，所以外层的时间复杂度是O（n）,

因为需要比较每个子串和匹配串，所以内层循环的时间复杂度是O（m）。

所以暴力破解法求解字符串匹配的时间复杂度是O（m*n）。

在匹配模式串的过程中，可能会出现匹配若干字符之后出现不匹配的情况，该情形下，暴力破解会将位置回退至开始匹配位置的下一位，匹配过程中已经匹配过的字符需要重新进行匹配，而KMP可以避免此类情形下的回退，使得时间复杂度减少为O（n）。

KMP利用已经和模式串匹配的特点，而不需要将文本串回退，只回退模式串。

例如模式串如果是aafbcbaafz，如果文本串匹配到模式串最后以为发现不相等。

根据匹配的特点，文本串在发生不匹配之前的字符串是aafbcbaaf，

如果将文本串的文字直接回退到当前文本串开始位置的下一个字符，接着的文本串是afbcbaaf，和模式串肯定是不能完全匹配的，所以这种大范围回退没有意义。

但是文本串在发生不等之前的三个字符是aaf，

而模式串的前三个字符也是aaf，

此时不需要回退文本串，而如果模式串从第四个字符开始，此时可以继续比对。

以上思想就是最长公共前后缀。

在KMP算法中，模式串每个位置上计算出来的最长公共前后缀一般被称为next数组。

有了next数组，在匹配失败的时候，文本串不回退，模式串直接回退到next数组的位置继续开始匹配即可。

通过代码来实现对 next 数组的求解首先需要next数组的递推关系。

对于模式串的位置j，有next[j] = k，则对于模式串的位置j + 1，可以分为以下两种情况：

若 p[k] == p[j]，则可以推到出来next[j + 1] = next[j] + 1；

若 p[k] != p[j]，则如果k = next[k]，并且 p[k] == p[j]，next[j + 1] = k + 1，否则重复此过程。