LeetCode|LeetCode 28. 实现 strStr()（KMP、字符串） KMP算法|C++|LeetCode

上一篇博客：LeetCode 27. 移除元素（双指针）

?写在前面：大家好！我是ACfun,我的昵称来自两个单词Accepted和fun。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油，冲鸭！
?用知识改变命运，用知识成就未来！加油 (? ??o??)? (? ??o??)?

原题链接：LeetCode 28. 实现 strStr()

文章目录

题目信息

题目描述
示例

示例 1
示例 2

说明

题解

暴力解法（滑动窗口）

解题思路
解题代码
时间复杂度
提交结果

KMP解法

解题思路
解题代码
时间复杂度
提交结果

题目信息题目描述 【LeetCode|LeetCode 28. 实现 strStr()（KMP、字符串）】实现 strStr() 函数。
?给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例示例 1

输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

说明 ?当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
?对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
题解暴力解法（滑动窗口）解题思路
?我们可以使用 C++ STL string类的 compare() 函数不断的从 haystack 取出长度为 needle.length() 的子串与 needle 进行比较，成功则返回当前子串的头指针即可。如果一直遍历到最后一个子串也没有匹配上的话就返回 -1。
?在 C++ 中使用 compare() 函数需要引入 include 头文件。compare()函数主要有四个重载函数，在本题中我们使用的函数为：

int compare(index, length, &str ); // index:子串的开始下标 // length:子串的长度 // &str:与子串进行比较的字符串

例如：

#include #include using namespace std; int main() { string str1, str2; cin >> str1 >> str2; // 输入str1, str2 cout << str1.compare(str2); // 比较str1和str2 cout << endl; // 比较str1第一个与str2长度相等的子串与str2 cout << str1.compare(0, str2.length(), str2); return 0; }

?在 compare() 函数返回的结果有三种：

返回值 大于0 说明 str1 < str2
返回值 等于0 说明 str1 == str2
返回值 大于0 说明 str1 > str2

注意: compare() 是按照字符串的字典序进行比较的，并不是字符串的长度。
?明白了 compare() 函数的用法那么本题就很简单了，我们只要将长度为 needle.length() 的滑动窗口沿着 haystack 字符串逐步移动，并将窗口内的子串与 needle 字符串相比较，如果结果返回 0 说明匹配到了，那么我们直接返回开始的下标即可。如果函数遍历完整个字符串都没有匹配到说明没有与 needle 相同的子串，此时 return -1 即可。

LeetCode|LeetCode 28. 实现 strStr()（KMP、字符串）

文章图片

解题代码

class Solution { public: int strStr(string haystack, string needle) { int haystack_len = haystack.length(), needle_len = needle.length(); for (int i = 0; i < haystack_len - needle_len + 1; i++) { if (haystack.compare(i, needle_len, needle) == 0) return i; } return -1; } };

时间复杂度
?假设字符串 haystack 的长度为 N，needle 的长度为 L。因为需要依次进行滑动遍历，所以时间复杂度为 *O((N - L)L)
提交结果

文章图片

KMP解法解题思路
?本题也可以使用 KMP算法来解决，KMP算法虽然在刚接触的时候不太好理解，但是是一种效率比较高的串的模式匹配算法。KMP算法可以在 O(m + n) 的时间数量级上完成串的匹配操作。相对于暴力解法，其改进在于不用依次进行循环遍历，而是利用已经得到的 “部分匹配” 的结果将比较的串向后 "滑动” 尽可能远的一段距离后继续进行匹配，省去了很多无用功。
?有关 KMP算法的具体实现大家可以看看B站UP主正月点灯笼的讲解视频：
?KMP字符串匹配算法1
?KMP字符串匹配算法2
灯神讲的非常好，其他的算法也讲的很棒，宝藏UP，强烈推荐哈哈。
解题代码

class Solution { public: int strStr(string haystack, string needle) { if (needle.empty()) return 0; // 求前缀表 vector prefix_table(needle.length() + 1); prefix_table[0] = 0; int len = 0, i = 1; while (i < needle.length()) { if (needle[i] == needle[len]) { len++; prefix_table[i] = len; i++; } else { if (len > 0) { len = prefix_table[len - 1]; } else { prefix_table[i] = len; i++; } } } // 将前缀表的向后移动一位，并将第一位改为 -1 for (int j = prefix_table.size() - 1; j > 0; j--) { prefix_table[j] = prefix_table[j - 1]; } prefix_table[0] = -1; // KMP_search int k = 0, j = 0; while (k < haystack.length()) { if (j == needle.length() - 1 && haystack[k] == needle[j]) { return k - j; } if (haystack[k] == needle[j]) { k++; j++; } else { j = prefix_table[j]; if (j == -1) { k++; j++; } } }return -1; } };

时间复杂度
?O(m +n)
提交结果