LeetCode28 Implement strStr

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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;
}
};
分享到 评论