1、描述
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。
示例 1:
输入:haystack = “sadbutsad”, needle = “sad”
输出:0
解释:“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。
示例 2:
输入:haystack = “leetcode”, needle = “leeto”
输出:-1
解释:“leeto” 没有在 “leetcode” 中出现,所以返回 -1 。
2、关键字
字符串匹配
3、思路
暴力
kmp算法 ,找next数组,s和p都在前边加一个‘ ’空格,
4、notes
背模板
5、复杂度
时间O(m + n)
空间O(n)
6、code
# kmp算法
class Solution {
public:
void findNext(string p, vector<int>& next) {
for(int i = 2, j = 0; i <p.size() ; i++) {
while(j > 0 && p[i] != p[j + 1]) j = next[j];
if(p[i] == p[j + 1]) j++;
next[i] = j;
}
}
int strStr(string s, string p) {
int n = s.length();
int m = p.length();
if(m == 0) return 0;
s.insert(s.begin(), ' ');
p.insert(p.begin(), ' ');
vector<int>next(m + 1);
findNext(p, next);
// 匹配
for(int i = 1, j = 0; i <= n; i++) {
while(j > 0 && s[i] != p[j + 1]) j = next[j];
if(s[i] == p[j +1]) j++;
if(j == m) return i - m;
}
return -1;
}
};
# 暴力
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
int res = -1;
for(int i = 0; i<= n - m; i++) {
int cnt = 0;
for(int j = 0; j < m; j++) {
if(haystack[i + j] == needle[j]) {
cnt++;
} else {
break;
}
}
if(cnt == m){
res = i;
break;
}
}
return res;
}
};