成都电商平台网站设计,网站项目计划书,买一个app需要多少钱,代码开源网站1. 问题引入
链接#xff1a;leetcode_28
题目#xff1a;s1字符串是否包含s2字符串#xff0c;如果包含返回s1中包含s2的最左开头位置#xff0c;不包含返回-1
暴力方法就是s1的每个位置都做开头#xff0c;然后去匹配s2整体#xff0c;时间复杂度O(n*m)
KMP算法可以…1. 问题引入
链接leetcode_28
题目s1字符串是否包含s2字符串如果包含返回s1中包含s2的最左开头位置不包含返回-1
暴力方法就是s1的每个位置都做开头然后去匹配s2整体时间复杂度O(n*m)
KMP算法可以做到时间复杂度O(nm)那这个算法是怎样实现的呢 2. 核心概念最长公共前后缀
对于某个字符不含该字符前面的字符串的前后缀最大匹配长度需要把这些数值传给一个数组(next数组)下标 i 表示第 i 个字符前的字符串(即从 0 ~ i-1 的字符串)的前后缀最大匹配长度
非常不好理解请看示例 这个玩意有什么用呢看后面的核心步骤就理解了。 3. 核心过程 【过程分解】 在比对的过程中有两个数 xy 记录两者对比到的下标 1当两字符相同同时xy继续对比下一个数据就好了 2当s1和s2对应的字符不匹配时则将y跳转到next数组对应数据下标的字符在此例子中是将y跳转到下标6的位置 PS每次跳转时如果此时y为0只需要x即可因为y已经没有可以再退的字符了 跳转之后 此时x和y对应的下标依旧不匹配再按照之前的逻辑找此时y对应的next数组的数据并跳转应该跳转到3 再跳转后 当x和y对应的字符相同时在xy看下一个字符是否匹配但是因为x已经越界但s2还没匹配完说明匹配失败返回 -1 【总结】
一共有两种情况分别是
两字符相同同时xy看后续是否相同两字符不同但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();vectorint 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;}};
