网站建设话术开场白,望京网站建设公司,郑州网站建设哪里好,网站邮件推送文章目录实现 strStr()习题暴力解法kmp 解法实现 strStr()
本节对应代码随想录中#xff1a;代码随想录#xff0c;讲解视频#xff1a;帮你把KMP算法学个通透#xff01;#xff08;理论篇#xff09;_哔哩哔哩_bilibili、帮你把KMP算法学个通透#xff01;#xff0…
文章目录实现 strStr()习题暴力解法kmp 解法实现 strStr()
本节对应代码随想录中代码随想录讲解视频帮你把KMP算法学个通透理论篇_哔哩哔哩_bilibili、帮你把KMP算法学个通透求next数组代码篇_哔哩哔哩_bilibili
习题
题目链接28. 找出字符串中第一个匹配项的下标 - 力扣LeetCode
给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。
示例 1
输入haystack sadbutsad, needle sad
输出0
解释sad 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 所以返回 0 。暴力解法
题目意思是 needle 字符串是否在 haystack 字符串中出现如果出现返回第一次出现的位置
那么直观的解法就是遍历 haystack 字符串不断地将当前字符串与 needle 第一个字符比较如果相同则再依次比较后续长度的元素是否还是等于 needle 对应位置的元素。需要注意的是遍历 haystack 字符串的边界条件是 ineedle.size()haystack.size()因为一旦剩余的 haystack 字符串小于 needle 的长度那肯定无法匹配避免 haystack[ij] 可能出现数组越界的情况
class Solution {
public:int strStr(string haystack, string needle) {int n haystack.size(), m needle.size();// 循环遍历haystacki表示当前检查的位置for (int i 0; i m n; i) {bool flag true;// 循环遍历needle字符串的每个字符for (int j 0; j m; j) {if (haystack[i j] ! needle[j]) { // 如果在某个字符处匹配失败则标记flag为false跳出循环flag false;break; } }if (flag) { // 如果整个needle字符串都匹配上了返回起始位置ireturn i;}}return -1;// 如果找不到needle字符串返回-1}
};时间复杂度O(m∗nm*nm∗n)。通过两层循环实现字符串匹配外层循环的次数是 n - m 1其中n是haystack的长度m是needle的长度内层循环的次数是needle的长度m。因此该算法的时间复杂度为 O(nm)空间复杂度O(111)。用了常量级别的额外存储空间因为只使用了几个整型变量和两个字符串形参不随着输入数据量的变化而变化。因此该算法的空间复杂度为 O(1)
kmp 解法
这道题主要还是考察 kmp。上面的暴力解法一旦不匹配我们是向后移动一位再尝试匹配而 kmp 则优化了这个移动的过程向后移动更多位来提高效率。简单来讲如下图kmp 是将公共前后缀的前缀移到了后缀的位置而不是像①一样只移动一位位置。
关于 kmp 的理论建议先看这个视频【天勤考研】KMP算法易懂版_哔哩哔哩_bilibili了解下原理。再去看代码随想录的视频熟悉代码该怎么写。 那么每次不匹配的时候该移动多少呢这就涉及到 next 数组的构建。在进行字符串匹配的时候我们先构建 next 数组用来记录每个位置的公共前后缀长度之后当不匹配的时候直接根据 next 数组进行移动。
class Solution {
public:// 获取next数组用于字符串匹配void getNext(int* next, const string s) {// ①初始化next数组第一个值为0int j 0;next[0] 0; // 循环遍历s中每个字符for(int i 1; i s.size(); i) { // ②前后缀不相同while (j 0 s[i] ! s[j]) {j next[j - 1]; //若匹配失败则回溯到之前的状态继续匹配}// ③前后缀相同if (s[i] s[j]) { //若当前字符和目标匹配j; //将匹配数量1}// ④更新next数组next[i] j; //将新的匹配数量重新赋值至next数组}}// 实现字符串匹配算法int strStr(string haystack, string needle) {int next[needle.size()];getNext(next, needle); //获取needle字符串的next数组int j 0; //j代表子串needle中已经匹配到的字符个数// 循环遍历haystack中的每个字符for (int i 0; i haystack.size(); i) { while(j 0 haystack[i] ! needle[j]) {j next[j - 1]; //回溯将j移动到目前匹配的最长公共前后缀的结尾处}if (haystack[i] needle[j]) { //如果当前字符匹配成功j; //继续匹配下一个字符}if (j needle.size() ) { //如果匹配成功返回子串在字符串中的位置return (i - needle.size() 1);}}return -1; //匹配失败返回-1}
};时间复杂度O(mnmnmn)。其中 m 和 n 分别为 haystack 和 needle 字符串的长度。在 strStr 函数中有一个 while 循环嵌套在 for 循环中循环次数最多为 haystack 字符串长度 m 加上 needle 字符串长度 n所以时间复杂度为 O(mn)空间复杂度O(nnn)。定义了一个 int 数组 next其长度为 needle 字符串长度 n所以空间复杂度为 O(n)
