問題
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
例子
yreuhudewj hud
4
分析
假設(shè)被搜索的字符串為S融撞，要搜索的字符串為T草穆。
- 方法一：遍歷S的每一個位置廉邑，從當(dāng)前位置開始匹配T萨螺。如果匹配成功儿倒，返回當(dāng)前位置泛领；如果不成功狠角，繼續(xù)遍歷下一個位置绒瘦。
- 方法二：kmp算法巴碗。有時間再仔細(xì)研究朴爬。
要點
brute-force即可
時間復(fù)雜度
- 方法一： O(mn)
- 方法二： O(m+n)
空間復(fù)雜度
- 方法一： O(1)
- 方法二： O(n)
代碼
方法一
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle == "") return 0;
if (haystack == "" || haystack.size() < needle.size()) return -1;
for (int i = 0; i <= haystack.size() - needle.size(); i++) {
int j = 0;
for (; j < needle.size(); j++)
if (haystack[i + j] != needle[j]) break;
if (j == needle.size()) return i;
}
return -1;
}
};
方法二
class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.length(), n = needle.length();
if (!n) return 0;
vector<int> lps = kmpProcess(needle);
for (int i = 0, j = 0; i < m; ) {
if (haystack[i] == needle[j]) {
i++;
j++;
}
if (j == n) return i - j;
if (i < m && haystack[i] != needle[j]) {
if (j) j = lps[j - 1];
else i++;
}
}
return -1;
}
private:
vector<int> kmpProcess(string& needle) {
int n = needle.length();
vector<int> lps(n, 0);
for (int i = 1, len = 0; i < n; ) {
if (needle[i] == needle[len])
lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
return lps;
}
};
