上一篇博客：LeetCode 27. 移除元素（双指针）
写在前面：大家好！我是
ACfun,我的昵称来自两个单词Accepted和fun。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油，冲鸭！
用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง
原题链接：LeetCode 28. 实现 strStr()
文章目录
- 题目信息
- 题目描述
- 示例
- 示例 1
- 示例 2
- 说明
- 题解
- 暴力解法（滑动窗口）
- 解题思路
- 解题代码
- 时间复杂度
- 提交结果
- 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<string> 头文件。compare()函数主要有四个重载函数，在本题中我们使用的函数为：
int compare(index, length, &str );
// index:子串的开始下标
// length:子串的长度
// &str:与子串进行比较的字符串
例如：
#include<iostream>
#include<string>
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 即可。
解题代码
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<int> 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)
提交结果
这个提交结果让我感到很意外，竟然比暴力法击败数更低！但是不能否认 一般情况下 KMP算法 确实是比 暴力算法 要好很多。
未完待续，持续更新中……
