题目描述
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
KMP解法 — 需要 KMP 知识
class Solution
{
public
:
vector
<int> PrefixFun(string needle
) {
int m
= needle
.size();
vector
<int> pi(m
);
int k
= 0;
for (int i
= 1; i
< m
; i
++) {
while (k
> 0 && needle
[k
] != needle
[i
])
k
= pi
[k
-1];
if (needle
[k
] == needle
[i
])
k
= k
+1;
pi
[i
] = k
;
}
return pi
;
}
int strStr(string haystack
, string needle
) {
int haSize
= haystack
.size();
int neSize
= needle
.size();
if (neSize
== 0) return 0;
vector
<int> PF
= PrefixFun(needle
);
int i
= 0, j
= 0;
while (i
< haSize
) {
if (haystack
[i
] == needle
[j
]) {
if (j
== neSize
-1) return i
-neSize
+1;
j
++; i
++;
}
else if (j
== 0) i
++;
else j
= PF
[j
-1];
}
return -1;
}
};
内置函数解法 — find函数 方便快捷
class Solution
{
public
:
int strStr(string haystack
, string needle
) {
if (needle
.empty()) return 0;
int pos
= haystack
.find(needle
);
if (pos
== -1) return -1;
return pos
;
}
};
原始暴力解法 — 效率低下
class Solution
{
public
:
int strStr(string haystack
, string needle
) {
if (needle
.length() == 0) return 0;
int j
, ndl
= needle
.length();
for (int i
= 0; i
< haystack
.length(); i
++) {
j
= 0;
for (j
= 0; j
< ndl
; j
++) {
if (needle
[j
] != haystack
[i
+ j
]) break;
}
if (j
== ndl
) return i
;
}
return -1;
}
};
参考
https://leetcode.com/problems/implement-strstr/discuss/13257/4ms-c-code-using-kmp-algorithm
https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-c-by-gpe3dbjds1/
分析
KMP
要学会第一种方法就必须弄懂 KMP 方法。我看的是YouTube上的一个讲解的视频。有字幕语速也不算快，可以试试：https://www.youtube.com/watch?v=GTJr8OvyEVQ；这个方法的精髓，个人认为就是存储了找到了匹配的前缀后可以存起来，使以后的匹配更加轻松。先对 pattern 部分进行处理，每个字母会对应一个值。i 和 j 分别从 0 和 1 处开始，如果text[i] == text [j]。对应字母 text[i] 的值为 j += 1。如果二者不等，字母 text[i] 的值是 text[j - 1] 字母对应的值，j 返回 0处。然后根据 pattern 处理 text，处理 text 时会有 两个名词：prefix 和 suffix：前缀和后缀。解释是：在匹配过程中遇到某个字母不匹配的情况时，无法匹配的字符它左、右的字符串分别被称为前缀、后缀。匹配过程：匹配继续前进。不匹配时，去 pattern 的前一个字母看它对应的值是多少，然后去对应下标的字母继续匹配。建议看看视频，加上我的描述，会很好懂。代码中的两部分，第一个函数做前缀处理，另一个做匹配。弄明白方法了很好懂，不再赘述。
内置函数解法
bug 一样的存在。调一下就可以了，没什么好说的。
暴力解法
暴力解法，就是以 haystack 中每个字母为入口，然后从 needle 字符串的开头、现在的下标 i 开始做匹配。如果匹配到最后还匹配，那么输出开始的位置。
小总结
我觉得能用简单的逻辑、调用函数做出题目，当然好。说明自己有一定的代码、逻辑能力。但是，算法也是我们技能背包里必备的东西。所以我认为这道题目最值得学习的是 KMP 解法。而且也淡化了对其他方面的描述，着重 KMP 原理。如果啃不下了那么多啃几次，一定能啃出来！相信自己，加油！
