28.找出字符串中第一个匹配项的下标
1.暴力求解
思路
对原串的每一个前缀进行搜索，判断是否和模式串相匹配。
实现
点击查看代码
class Solution {
public:
int strStr(string haystack, string needle) {
for(int i = 0; i < haystack.size(); i++){
for(int j = i; j < i+needle.size()+i; j++){
if(haystack[j] != needle[j-i])break;
if(j == i+needle.size()-1)return i;
}
}
return -1;
}
};
复杂度分析
- 时间复杂度：O(n * m)
- 空间复杂度：O(1)
2.kmp
思路
相当于对暴力进行化简，减少了对于重复的匹配。
讲解
实现
点击查看代码
class Solution {
public:
void getNext (int *next,string needle){
next[0] = 0;
int j = 0;
for(int i = 1; i < needle.size(); i++){
while(j >= 1 && needle[i] != needle[j]){
j = next[j-1];
}
if(needle[i] == needle[j]){
j++;
}
next[i]=j;
}
}
int strStr(string haystack, string needle) {
int m = haystack.size();
int n = needle.size();
int next[n];
getNext(next,needle);
int j = 0;
for(int i = 0; i < m; i++){
while(j > 0 && haystack[i] != needle[j]){
j = next[j-1];
}
if(haystack[i] == needle[j]){
j++;
}
if(j == n)return i-j+1;
}
return -1;
}
};
复杂度分析
- 时间复杂度：O(n + m)
- 空间复杂度：O(n)