儋州网站建设建立网站用英语
1. 问题引入
链接：leetcode_28
题目：s1字符串是否包含s2字符串，如果包含返回s1中包含s2的最左开头位置，不包含返回-1
暴力方法就是s1的每个位置都做开头，然后去匹配s2整体，时间复杂度O(n*m)
KMP算法可以做到时间复杂度O(n+m)，那这个算法是怎样实现的呢？
2. 核心概念：最长公共前后缀
对于某个字符，不含该字符，前面的字符串的前后缀最大匹配长度，需要把这些数值传给一个数组(next数组)，下标 i 表示第 i 个字符前的字符串(即从 0 ~ i-1 的字符串)的前后缀最大匹配长度
非常不好理解，请看示例：
这个玩意有什么用呢，看后面的核心步骤就理解了。
3. 核心过程
【过程分解】
在比对的过程中，有两个数 x，y 记录两者对比到的下标
1）当两字符相同，同时x++，y++，继续对比下一个数据就好了
2）当s1和s2对应的字符不匹配时，则将y跳转到next数组对应数据下标的字符，在此例子中是将y跳转到下标6的位置
PS：每次跳转时，如果此时y为0，只需要x++即可，因为y已经没有可以再退的字符了
跳转之后：
此时x和y对应的下标依旧不匹配，再按照之前的逻辑，找此时y对应的next数组的数据，并跳转，应该跳转到3
再跳转后：
当x和y对应的字符相同时，在x++，y++看下一个字符是否匹配，但是因为x已经越界，但s2还没匹配完，说明匹配失败，返回 -1
【总结】
一共有两种情况分别是
- 两字符相同，同时x++，y++，看后续是否相同
- 两字符不同，但y在下标0位置，只需要x++；若y不在0位置，将y定位到对应next数组相应数据的位置
在每一次操作结束时，都需要判断x和y是否已经越界
如果y等于s2的长度(包括x和y同时越界和只有y越界)，则说明匹配成功，结果为x-y （情况1）
否则，x越界，y没越界，说明匹配失败，返回-1 （情况2）
此处对应代码的return返回值
【解惑】
1）为什么s2的0~5下标的字符和s1的7~12下标的字符对应，可以直接不用比对？
2）如果在s1的7下标之前还有与s2配对吗？
没有了，因为next数组就已经决定了这是最长的前后缀匹配长度，再长就不匹配了
-
为什么会加速？
每次匹配时只需要从该字符对应的 next 数组的数开始匹配，相当于跳过了一部分的数据对比过程
【next 数组的创建】
有点类似动态规划，通过前面的已知数据，推出当前的数据
操作过程：
若前一位的字符，与其next数组对应的下标的字符相同，则该字符对应的数为此下标数+1
如果不相同，若 next 数组对应数据不为0，则跳转到对应下标，若为0则此字符对应 next 值为0
4. 例题
如果还不是很清晰，可以结合模版题和代码一起分析，会更好理解
模版题：链接
参考代码：
class Solution {
public:int strStr(string s1, string s2) {int m = s1.size(), n = s2.size();vector<int> next(n + 5);next[0] = -1;next[1] = 0; // 0和1下标next值默认确定int i = 2, cn = 0; // i表示当前对应下标，cn表示next值// 生成next数组// 结合前面的分析进行情况分类while (i < n){if (s2[i - 1] == s2[cn])next[i++] = ++cn;else if (cn > 0)cn = next[cn];elsenext[i++] = 0;} int x = 0, y = 0;// x表示s1当前比对的位置// y表示s2当前比对的位置while (x < m && y < n){if (s1[x] == s2[y]){x++;y++;}else if (y == 0)x++;elsey = next[y]; }return y == n ? x - y : -1;}};