LeetCode28 Implement strStr


描述

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

样例

1
2
3
Input: 
abca
ca
1
2
Output: 
2

思路

实现strStr()函数。该函数是用来在s串中查询是否存在串t的,若存在则返回第一次出现的下标。

字符串匹配的模板题,使用KMP算法即可。注意要特判串t为空的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
int* fail;
public:
void getFail(string s) {
int i = 0, j, n = s.size();
fail = new int[n + 1];
j = fail[0] = -1;
while (i < n) {
while (j != -1 && s[i] != s[j]) j = fail[j];
fail[++i] = ++j;
}
}
int strStr(string haystack, string needle) {
if (needle == "") return 0;
getFail(needle);
int i = 0, j = 0;
int n = haystack.size(), m = needle.size();
while (i < n) {
while (j != -1 && haystack[i] != needle[j]) j = fail[j];
++i; ++j;
if (j == m) return i - m;
}
return -1;
}
};