题目
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = “hello”, needle = “ll”
Output: 2
Example 2:
Input: haystack = “aaaaa”, needle = “bba”
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().
解法
- 使用 KMP 算法时：算法复杂度
O(n+m)，空间复杂度O(m) - 时间复杂度：O(n*m)
思路
- 使用普通的搜索算法去搜索时，就是按部就班去搜索，挨个匹配。这个也是
search算法。 - KMP：
代码
class Solution {
private:
int useSearch(string haystack, string needle) {
if (needle.empty()) return 0;
auto pos = search(haystack.begin(), haystack.end(), needle.begin(), needle.end());
if (pos == haystack.end()) {
return -1;
} else {
return distance(haystack.begin(), pos);
}
}
int useKMP(string haystack, string needle) {
if (needle.empty()) return 0;
if (haystack.empty()) return -1;
int needle_size = needle.size();
int stack_size = haystack.size();
int i = 0;
int j = -1;
vector<int> next(needle_size, -1);
next[0] = -1;
/* build next */
/*
cout << "start to build pattern: " << needle_size << ", " << stack_size << endl;
cout << "stack: " << haystack << " needle: " << needle << endl; */
while (i < needle_size) {
while (j > -1 && needle[i] != needle[j]) {
j = next[j];
}
++i;++j;
/* cout << "i: " << i << " j: " << j << endl; */
if (i >= needle_size) break;
if (needle[i] == needle[j]) {
next[i] = next[j];
} else {
next[i] = j;
}
}
/* cout << "pattern build finish" << endl;
copy(next.begin(), next.end(), ostream_iterator<int>(cout, ","));
cout << endl << "next[0] = " << next[0];
cout << "next[1] = " << next[1] << endl;
*/
/* search */
i = 0; j = 0;
while (i < stack_size) {
while (j > -1 && haystack[i] != needle[j]) {
j = next[j];
}
++i;
++j;
if (j == needle_size) {
return i - j;
}
}
// delete [] next;
return -1;
}
public:
int strStr(string haystack, string needle) {
return useKMP(haystack, needle);
}
};
本文完