# Implement strStr

Posted by chunyang on April 6, 2019

### 题目

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);
}
};