1. 题目描述 28. 实现 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
2. 思路1 暴力求解
暴力求解思路比较简单，即在模式串和主串进行匹配的过程中，如果发现某个字符不匹配，则模式串从头开始，主串的指针回退到上一次开始位置的下一个位置，直到主串遍历完毕，或者提前匹配成功。
遍历主串所用的时间复杂度是，而每次从一个字符开始的时候，都需要依次和模式串的每个字符进行比较，故总体时间复杂度为
，但是通常
所以该方法的时间复杂度其实也不是很高，因而效率依然还是不错。
代码如下
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function (haystack, needle) {
let needle_len = needle.length
if (needle_len === 0) return 0
let res = -1
for (let i = 0; i < haystack.length; i++) {
// 如果第一个字符匹配上，则判断接下来的几个字符是不是相同
if (haystack[i] === needle[0]) {
if (haystack.substring(i, i + needle_len) === needle) {
res = i
break
}
}
}
return res
}
3. 思路2 KMP算法求解
KMP算法相比于暴力求解方法的优点在于，暴力求解每次匹配失败都会使得主串的指针回溯，而KMP算法则不会使得主串指针回溯，我们来通过例子理解一下。
从头开始匹配，当匹配到的时候，发现该字符匹配不上，主串的指针则会回退到
b，与模式串重新开始匹配，具体过程如下
我们可以看到，暴力匹配的方式需要这样老实巴交的执行，才能发现匹配不成功。但是在①的时候，即匹配不成功时，我们发现之前的都是匹配上的，且匹配上的部分有前缀和后缀均为
的子串，在KMP算法中，我们不需要回溯主串指针，直接将模式串从真前缀位置
移动到真后缀
位置，即一下可以跳过步骤②和③直接到达④进行后续匹配。
为什么可以这么做呢？
因为我们在发现当匹配不上的时候，我们希望模式串有一个字符能够替代
使得匹配继续进行，这时候我们发现，如果前面有真前缀和真后缀配对的话，那么我们可以用真前缀替换真后缀，使得模式串向后移动，真前缀的下一个字符则可以替代真后缀的下一个字符，也就是当前没有匹配上的
从而使得匹配继续进行。不过需要注意的是，如果我们每次都去寻找真前缀和真后缀的话，实际上是很慢的！
这时候我们又发现了一个规律，当出现匹配不上字符的时候，模式串和主串在这个字符之前是完全匹配上的，那么说明寻找真前缀和真后缀压根和主串没有啥关系，只需要找模式串即可。我们定义一个数组，其中
表示
最长真前缀的长度
以本例的模式串为例，我们来计算一下数组的值
pi[0] = 0, a没有真前缀
pi[1] = 0, ab没有真前缀
pi[2] = 0, abc没有真前缀
pi[3] = 1, abca有真前缀a
pi[4] = 2, abcab有真前缀ab
pi[5] = 0, abcabe没有真前缀
不难发现，数组有几个重要的性质：
-
，即
的下一位的数值最多比当前值递增1。
- 当
及
时，有
。
那么我们在构造数组的时候，只需要执行如下操作：
1. 定义一个数组，长度等于模式串的长度，且pi[0] = 0
2. 令i = 1,j = 0开始遍历，如果pattern[i] != pattern[j]则说明未匹配成功，
我们需要将j指针回退到一个可以使得pattern[i] == pattern[j]的位置，根据性质2，
令j = pi[j - 1]
若j回退到0的位置，则表示未找到这样一个合适位置，pi[i] = 0，i从下一个字符开始
3. 如果pattern[i] == pattern[j]，说明匹配成功，根据性质2，pi[i] = j+1
具体构造数组的代码如下
/**
* 构建pi数组
* @param {string} pattern 模式串
*/
const getPi = (pattern) => {
let i = 1,
j = 0,
m = pattern.length
const pi = new Array(m).fill(0)
while (i < m) {
// 未匹配成功，j进行回溯，若回溯到j=0则表示不存在这样的真前缀
// 回溯取j=pi[j-1]一步步向前试探
while (j > 0 && pattern[i] !== pattern[j]) {
j = pi[j - 1]
}
// 如果匹配上，则 pi[i] = j+1, 且i和j后移
if (pattern[i] === pattern[j]) {
pi[i++] = ++j
// 如果j为0，则表示没真前缀，此时pi[i] = j, i和j后移
} else if (j === 0) {
pi[i++] = j
}
}
return pi
}
有了预定义的数组我们就可以开始进行KMP算法了。
1. 让主串和模式串的指针i和j分别从下标0开始匹配
2. 如果主串和模式串出现了字符不匹配，那么j需要进行回退到一个合适位置
即j = pi[j-1]，如果j=0了，说明i从该字符开始无法找到匹配子串，i++
3. 如果匹配上，则i和j都向后移动
4. 如果j的值等于模式串长度，则说明找到了，返回此时子串的起始位置
5. 其他情况为未找到，返回-1
代码如下
/**
* KMP算法实现
* @param {string} s 主串
* @param {string} pattern 模式串
*/
const strStr = (s, pattern) => {
const n = s.length,
m = pattern.length
if (m === 0) return 0 // c语言的结果
const pi = getPi(pattern)
// 执行Kmp匹配过程
for (let i = 0, j = 0; i < n; i++) {
// 出现了某个字符不匹配的情况，需要j进行回溯
while (j > 0 && s[i] !== pattern[j]) {
j = pi[j - 1]
}
// 匹配成功，此时j++，循环结束后i++
if (s[i] === pattern[j]) {
j++
}
if (j === m) {
// 匹配成功
return i - j + 1
}
}
return -1
}
