#每日一题#实现函数：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）如果不存在，则返回 -1
我的前端面试题练习》》》#每日一题
问题描述：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr
实现strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1
示例 3：
输入：haystack = "", needle = ""
输出：0
提示：
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成
我的 错误解答：（注意：是错误解答，正确解答，在后面）
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
var len=needle.length;
if(needle==''){
return 0;
}else{
var s=haystack.indexOf(needle)
if(s){
return s
}else{
return -1
}
}
};
我的记录：
提交得结果是错误，
原因分析：
我进行了以下测试：
在将该函数的l两个参数都传入为"a"的时候，按照逻辑，应该输出0，但是我们这里的结果输出的却是-1，
仔细检查代码，我发现，这里输入-1的原因是因为，我在判断s的时候，没有考虑到s的值是下标的值，在这里下标是从0开始的，也就是说，当我们这里的s为0的时候，就跳出了该if语句，走到了它的else语句，从而输出-1，输出错误的结果。
解决方法：
在if判断中，将s的值加1，这样当s为0时，就不会影响判断。
正确代码：
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if(needle==''){
return 0;
}else{
var s=haystack.indexOf(needle)
if(s+1){
return s
}else{
return -1
}
}
};
官方解答：
前言
本题是经典的字符串单模匹配的模型，因此可以使用字符串匹配算法解决。 常见的字符串匹配算法： 包括暴力匹配、Knuth-Morris-Pratt 算法、Boyer-Moore 算法、Sunday 算法等，本文将讲解Knuth-Morris-Pratt 算法。
因为哈希方法可能出现哈希值相等但是字符串不相等的情况，而strStr 函数要求匹配结果必定正确，因此本文不介绍哈希方法，有兴趣的读者可以自行了解滚动哈希的实现（如 Rabin-Karp 算法）。
方法一：暴力匹配
思路及算法
我们可以让字符串needle 与字符串haystack 的所有长度为 m 的子串均匹配一次。
为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 -1。
代码：
var strStr = function(haystack, needle) {
const n = haystack.length, m = needle.length;
for (let i = 0; i + m <= n; i++) {
let flag = true;//假设haystack里面存在needle
//减少不必要的匹配：每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。
for (let j = 0; j < m; j++) {.
if (haystack[i + j] != needle[j]) {
flag = false;//当前匹配失败haystack里面不存在needle
break;
}
}
//
if (flag) {
return i;//haystack里面存在needle，并且下标开始为i
}
}
return -1;haystack里面不存在needle
复杂度分析
-
时间复杂度：
O(n×m)，其中 n 是字符串haystack的长度，m 是字符串needle的长度。最坏情况下我们需要将字符串needle与字符串haystack的所有长度为 m的子串均匹配一次。 -
空间复杂度：
O(1)。我们只需要常数的空间保存若干变量。
方法二：Knuth-Morris-Pratt 算法
思路及算法
Knuth-Morris-Pratt 算法，简称KMP 算法，由Donald Knuth、James H. Morris 和Vaughan Pratt 三人于 19771977 年联合发表。
Knuth-Morris-Pratt算法的核心为前缀函数，记作 π(i)，其定义如下：
对于长度为 m 的字符串 s，其前缀函数π(i)(0≤i<m)表示 s 的子串s[0:i]的最长的相等的真前缀与真后缀的长度。特别地，如果不存在符合条件的前后缀，那么π(i)=0。其中真前缀与真后缀的定义为不等于自身的的前缀与后缀。
我们举个例子说明：字符串aabaaab的前缀函数值依次为 0,1,0,1,2,2,3。
π(0)=0，因为 a 没有真前缀和真后缀，根据规定为 0（可以发现对于任意字符串π(0)=0必定成立）；
π(1)=1，因为 aa最长的一对相等的真前后缀为 a，长度为 1；
π(2)=0，因为aab 没有对应真前缀和真后缀，根据规定为 0；
π(3)=1，因为aaba 最长的一对相等的真前后缀为a，长度为 1；
π(4)=2，因为aabaa最长的一对相等的真前后缀为 aa，长度为 2；
π(5)=2，因为aabaaa最长的一对相等的真前后缀为aa，长度为 2；
π(6)=3，因为aabaaab最长的一对相等的真前后缀为aab，长度为 3。
有了前缀函数，我们就可以快速地计算出模式串在主串中的每一次出现。
如何求解前缀函数
长度为m 的字符串 s 的所有前缀函数的求解算法的总时间复杂度是严格O(m) 的，且该求解算法是增量算法，即我们可以一边读入字符串，一边求解当前读入位的前缀函数。
为了叙述方便，我们接下来将说明几个前缀函数的性质：
π(i)≤π(i−1)+1。
- 依据 π(i) 定义得：
s[0:π(i)−1]=s[i−π(i)+1:i]。 - 将两区间的右端点同时左移，可得
s[0:π(i−2]=s[i−π(i)+1:i−1]。 依据π(i−1)
定义得：π(i−1)≥π(i)−1，即π(i)≤π(i−1)+1。
- 如果
s[i]=s[π(i−1)]，那么π(i)=π(i−1)+1。
-
依据
π(i−1)定义得：s[0:π(i−1)−1]=s[i−π(i−1):i−1]。 -
因为
s[π(i−1)]=s[i]，可得s[0:π(i−1)]=s[i−π(i−1):i]。 -
依据π(i) 定义得：
π(i)≥π(i−1)+1，结合第一个性质可得 π(i)=π(i−1)+1。
这样我们可以依据这两个性质提出求解 π(i) 的方案：找到最大的 j，满足s[0:j−1]=s[i−j:i−1]，且s[i]=s[j]s[i]=s[j]（这样就有s[0:j]=s[i-j:i]s[0:j]=s[i−j:i]，即π(i)=j+1）。
注意这里提出了两个要求：
- j 要求尽可能大，且满足
s[0:j-1]=s[i-j:i1]s[0:j−1]=s[i−j:i−1] - j 要求满足
s[i]=s[j]s[i]=s[j]。
由π(i−1) 定义可知：
s[0:π(i−1)−1]=s[i−π(i−1):i−1] ----------- (1)
那么j=π(i−1)符合第一个要求。如果s[i]=s[π(i−1)]，我们就可以确定 π(i)。
否则如果s[i] ! =s[π(i−1)]，那么π(i)≤π(i−1)，因为j=π(i)−1，所以j < π(i−1)，于是可以取 (1) 式两子串的长度为 j的后缀，它们依然是相等的s[π(i−1)−j:π(i−1)−1]=s[i−j:i−1]。
当s[i] ! =s[π(i−1)]时，我们可以修改我们的方案为：找到最大的 j，满足s[0:j−1]=s[π(i−1)−j:π(i−1)−1]，且s[i]=s[π(i−1)]（这样就有s[0:j]=s[π(i−1)−j:π(i−1)]，即π(i)=π(i−1)+1。
注意这里提出了两个要求：
- j 要求尽可能大，且满足
s[0:j−1]=s[π(i−1)−j:π(i−1)−1]； - j 要求满足 s[i]=s[j]。
由π(π(i−1)−1) 定义可知j=π(π(i−1)−1) 符合第一个要求。如果s[i]=s[π(π(i−1)−1)]，我们就可以确定 π(i)。
此时，我们可以发现 j 的取值总是被描述为π(π(π(…)−1)−1) 的结构（初始为π(i−1)）。于是我们可以描述我们的算法：设定π(i)=j+1，j 的初始值为π(i−1)。我们只需要不断迭代 j（令 j 变为π(j−1)）直到s[i]=s[j]或j=0即可，如果最终匹配成功（找到了 j 使得s[i]=s[j]），那么π(i)=j+1，否则π(i)=0。
复杂度证明
- 时间复杂度部分，注意到
π(i)≤π(i−1)+1，即每次当前位的前缀函数至多比前一位增加一，每当我们迭代一次，当前位的前缀函数的最大值都会减少。可以发现前缀函数的总减少次数不会超过总增加次数，而总增加次数不会超过
m 次，因此总减少次数也不会超过 m 次，即总迭代次数不会超过 m 次。 - 空间复杂度部分，我们只用到了长度为 m 的数组保存前缀函数，以及使用了常数的空间保存了若干变量。
如何解决本题
记字符串haystack的长度为 n，字符串needle的长度为 m。
我们记字符串str=needle+#+haystack，即将字符串needle 和haystack 进行拼接，并用不存在于两串中的特殊字符# 将两串隔开，然后我们对字符串str求前缀函数。
因为特殊字符 # 的存在，字符串str 中haystack部分的前缀函数所对应的真前缀必定落在字符串needle 部分，真后缀必定落在字符串haystack 部分。当haystack 部分的前缀函数值为 m 时，我们就找到了一次字符串needle在字符串 haystack中的出现（因为此时真前缀恰为字符串needle）。
实现时，我们可以进行一定的优化，包括：
我们无需显式地创建字符串str。
为了节约空间，我们只需要顺次遍历字符串needle、特殊字符# 和字符串haystack即可。
也无需显式地保存所有前缀函数的结果，而只需要保存字符串needle 部分的前缀函数即可。
特殊字符# 的前缀函数必定为 0，且易知π(i)≤m（真前缀不可能包含特殊字符 #）。
这样我们计算π(i) 时，j=π(π(π(…)−1)−1)的所有的取值中仅有π(i−1) 的下标可能大于等于m。我们只需要保存前一个位置的前缀函数，其它的 j 的取值将全部为字符串needle部分的前缀函数。
我们也无需特别处理特殊字符#，只需要注意处理字符串haystack的第一个位置对应的前缀函数时，直接设定 j的初值为 0 即可。
这样我们可以将代码实现分为两部分：
- 第一部分是求
needle部分的前缀函数，我们需要保留这部分的前缀函数值。 - 第二部分是求
haystack
部分的前缀函数，我们无需保留这部分的前缀函数值。只需要用一个变量记录上一个位置的前缀函数值即可。当某个位置的前缀函数值等于 m
时，说明我们就找到了一次字符串needle在字符串haystack
中的出现（因为此时真前缀恰为字符串needle，真后缀为以当前位置为结束位置的字符串
haystack的子串），我们计算出起始位置，将其返回即可。
代码
var strStr = function(haystack, needle) {
const n = haystack.length, m = needle.length;
if (m === 0) {
return 0;
}
const pi = new Array(m).fill(0);
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = pi[j - 1];
}
if (needle[i] == needle[j]) {
j++;
}
pi[i] = j;
}
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = pi[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j === m) {
return i - m + 1;
}
}
return -1;
};
复杂度分析
- 时间复杂度：
O(n+m)，其中 n 是字符串haystack的长度，m 是字符串needle 的长度。我们至多需要遍历两字符串一次。 - 空间复杂度：
O(m)，其中 m 是字符串needle的长度。我们只需要保存字符串needle的前缀函数。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
来源：力扣（LeetCode）