字符串查找算法
发布时间：2021年7月28日
题目说明
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。leetCode地址
以下称 haystack 字符串为模式字符串简称模式串，needle 字符串为目标字符串简称目标串
示例
const haystack = 'hello world';
const needle = 'll';
strStr(haystack, needle); // 返回2特殊边际处理
在该题目中，存在一些边际问题，在此处进行统一说明，后续代码中注重讲解BF算法与KMP算法的核心思想，边际问题就不再赘述。
- 目标串
needle长度为0：该问题在题述中已经给出解决方案，返回0即可 - 目标串
needle的长度大于模式串haystack的长度：在模式串中肯定没有字符串与目标串相同，直接返回-1即可 - 目标串
needle与 模式串haystack的长度相同：直接两个字符串是否完全相同即可，相同返回0，不相同返回-1。
BF算法
思路
BF算法的思想其实很简单，取两个字符串不同位置上的字符进行对比。如果相同，向后对比，不相同时，回溯继续重新开始对比。
如：haystack 为 hello， needle 为 ll，最坏情况下依次判断 he、el、ll、lo是否完全和 ll 相等，相等即返回对应字符串在 haystack 中的下标。
详解
首先处理特殊边际情况，这块与第一种方法相同，就不再赘述。
以下为算法步骤：
设定两个指向变量，初始化为0，分别指向模式串
haystack和 目标串needle不同的位置的字符我们用
i代表指向模式串haystack的下标的变量，用j代表指向目标串needle的下标的变量。- 循环对比不同位置的字符，循环条件为两个指向变量
i和j均小于对应字符串的长度
- 循环对比不同位置的字符，循环条件为两个指向变量
如果
i和j分别指向的字符相等，将两个指向变量向后移动 1 位，即i++、j++继续对比如果不相等，将指向模式串的变量
i的回到本轮对比初始时的位置，并向后移动 1 位，并将目标串的指向变量j重置为0，重新开始对比。在这里，目标串的指向变量
j的值为本轮对比中已经匹配成功的长度，模式串的指向变量i的值为本次对比开始时的初始下标initI加上匹配成功的长度j，即initI = i - j，找到初始位置后，后移 1 位即是下次比对时应该指向长字符串的初始下标。我们一般称这个为回溯。当不满足循环条件时，就完成了所有字符的对比。
判断目标串的指向变量
j是否等于目标串自身的长度。如果相等，表明模式串haystack中最后一轮进行比对的子串与目标串needle完全相等，那么求出最后一轮比对子串的初始位置即可原理与第 4 步解释一致，我们返回的其实就是初始的下标。
代码
function strStr(haystack, needle) {
const hayLen = haystack.length;
const nedLen = needle.length;
if (!needle) {
return 0;
}
if (nedLen > hayLen) {
return -1;
}
if (nedLen === hayLen) {
return haystack === needle ? 0 : -1;
}
let hayIndex = 0;
let nedIndex = 0;
while (nedIndex < nedLen && hayIndex < hayLen) {
if (haystack[hayIndex] === needle[nedIndex]) {
hayIndex++;
nedIndex++;
} else {
hayIndex = hayIndex - nedIndex + 1;
nedIndex = 0
}
}
if (nedIndex === nedLen) {
return hayIndex - nedIndex;
}
return -1;
};leetcode 执行结果
BF改进算法 - KMP算法
思路
KMP算法可以看作是BF算法的优化版本，其核心思想在于减少目标串 needle 的移动次数即减少重新开始对的次数。
在BF算法中，遇到不匹配的情况时，都会放弃之前匹配的结果，将模式串向右移动并重制目标串 needle 回溯到第一个字符处，重新开始匹配。
那么如果存在这种情况：
在最后一次比对的子字符串中，前 n 位字符与后 n 位字符完全相等时，我们将目标串 needle 移动到某一个特定的位置，使得下一个重新匹配的子字符串的前 n 位与目标串的前 n 位完全相等，然后从第 n + 1 位处开始比较。
通过这种处理，我们就可以达到减少重新开始比对的次数的目的。这即是KMP算法的核心思想，匹配失败时将 needle 移动到合适的位置且从合适的位置再次开始匹配，减少匹配次数。
详解
理解KMP算法需要先明白两个概念：最长公共元素 以及 next 数组
最长长度表
最长长度表由最长公共元素组成的表。
上面我们说到在匹配失败时，将目标串 needle 移动到合适的位置处再次匹配。那么怎么确定要将目标串移动到那个的位置呢？此时，我们需要知道一个概念，叫最长长度表。这里的长度指的是目标串的每一个子字符串的 前缀 和 后缀 中最长相同元素的长度。
首先说明一下什么是一个字符串的前缀和后缀。假如一个字符串为 abba，那么该字符串的前缀为 [a, ab, abb]，后缀为 [bba, ba, a]。
即前缀为一个字符串除最后一位外的不同子串的集合，后缀为一个字符串除第一位外的不同子串的集合。而最大长度即是指前缀和后缀数组中最长相同字符串的长度。
因此我们知道了 abab 字符串的前后缀中相等的最长字符串为 a，即最长长度为1。
列出目标串中各子串的内容，依次求出其最长长度，绘制而成的表就是最长长度表。
比如 ABBACDA 字符串的求表过程为
| 子串 | 前缀 | 后缀 | 最长公共元素 |
|---|---|---|---|
| A | - | - | -，长度0 |
| AB | A | B | -，长度0 |
| ABB | A,AB | BB,B | -，长度0 |
| ABBA | AB,AB,ABB | BBA,BA,A | A，长度1 |
| ABBAC | A,AB,ABB,ABBA | BBAC,BAC,AC,C | -，长度0 |
| ABBACD | AB,ABB,ABBA,ABBAC | BBACD,BACD,ACD,CD,D | -，长度0 |
| ABBACDA | A,AB,ABB,ABBA,ABBAC,ABBACD | BBACDA,BACDA,ACDA,CDA,DA,A | A，长度1 |
最后，我们将各子串的最后一个字符取出来与最长长度形成一个对应关系，可以形成以下表
| 字符 | A | B | B | A | C | D | A |
|---|---|---|---|---|---|---|---|
| 最长公共元素长度 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
当在某一个字符处匹配失败时，我们在 最长公共长度表 中找到 最后匹配成功的字母 对应的子串所对应的最长长度。即当在第 i 位字符处匹配失败时，在第 i - 1 处字符处比对肯定是成功的（后续会讲到在第一位就失败时的处理方法），因此我们就可以得到最后匹配成功的子串前后缀中最长相同的长度。
为了方便从上面表中取值，我们将上面的表的长度数值整体右移一位，第一位填充一个特殊的标记值，为了方便后续处理，一般都设置该值为 -1。
对于右移后首位填充的值，没有说必须为
-1这个数字，只要是一个特殊的变量即可，你也可以设置为一个特殊的字符串，只要能够表明该值为我们手动添加的即可。在 KMP 算法中我们都默认给-1这个值是为了收拢所有比对失败的情况，避免在比对失败时，还要手动判断是否是在首位就比对失败的情况。
这样处理后，方便我们在匹配失败时获取最后依次匹配成功的子串的公共元素长度。我们将新产生的数组叫做 next 数组。
| 字符 | A | B | B | A | C | D | A |
|---|---|---|---|---|---|---|---|
| 最长公共元素长度 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| next值 | -1 | 0 | 0 | 0 | 1 | 0 | 0 |
next 数组的作用
通过上面描述，我们可以生成字符串前缀后缀的最长公共长度表以及 next 数组，那么我们要如何使用 next 数组呢？
我们看一个例子：
模式串为 ABACABAB，目标串为 ABAB，那么我们可以算出来 ABAB 的 next 数组
| 字符 | A | B | A | B |
|---|---|---|---|---|
| 最长公共元素长度 | 0 | 0 | 1 | 2 |
| next值 | -1 | 0 | 0 | 1 |
1.初始比对时，均从两个字符串的第 1 个字符开始匹配
A B A C A B A B
A B A B
⬆️匹配成功，继续向后比对
…省略后续比对成功过程
A B A C A B A B
A B A B
⬆️2.当匹配到第 4 个字符时，模式串的字符为 C ，目标串的字符为 B，比对失败。在我们求出的 next 数组中，next[4] 对应的值是 1，表明前方匹配成功的子字符串 ABA 中最长公共长度为 1 ，即 ABA 的第一位与最后一位是相同的，那么我们就可以通过将目标串的第二个字母 B 移动到上次比对失败的字母处，之所以这么移动，是因为目标串的前 1 位组成子串 A 与最后匹配成功的子串 A 相同，无需再次比对。
A B A C A B A B
⬆️ // 最后一次比对成功的位置
A B A B
⬆️ // 将目标串首位移动到该位置，两个字符肯定是相同的那么，我们如何实现这样的移动呢？
首先我们都知道，在没有参考系的情况下，两个物体之间的移动都是相对的，即当我们发现两个物体 A和B 之间发生了位移时，可能是 A 不动，B进行了移动 或者 A 进行移动，B 不动。因此，我们要实现字符串的移动，就会有以下两种方式：
我们先设定几个变量：
i：模式串当前的下标j：当前比对的长度，也就是在目标串中当前比对到的下标
- 模式串下标回溯。目标串下标归零(回溯)
在上面的匹配中，匹配成功的字符个数位为 3，且匹配成功字符串 ABA 的最长公共长度为1，那么 3 - 1 = 2就是模式串需要往后移动的位数。计算方式如下：
// 匹配失败时，先使得模式串的下标回到本次比对前的初始位置。
初始位置 = i - j;
// 模式串需要向后移动的位数为
移动位数 = j - next[j];
// 两者相加得到新一轮比对开始时模式串开始的下标
新下标 = i - j + j - next[j] = i - next[j];
// 最后使目标序号归零，重头开始比对
j = 0;但是我们上面说过KMP算法核心是长字符串下标不回溯，只移动匹配字符串的顺序，因此我们重点在第二个方法。
- 模式串下标不回溯，目标串移动位置
在第一个方法中我们是通过移动长字符串来实现匹配字符串的相对移动，那么如何是现在长字符串不移动情况下的匹配字符串移动呢？
还是通过一些变量来举例子，更好理解:
i和j变量的意义同上
如果在某一次对比中，模式串的第 i + 1 位 与 目标串的第 j + 1 位字符比对失败，我们保持模式串在 j + 1 这个位置不变，将目标串的下标回溯到 j - 1 的位置，就意味着我们将匹配字符串向后移动两位。
例子：
// 在 i = 3; j = 3处匹配失败
A B A C A B A B
A B A B
⬆️
// 我们保持模式串的下标不变，将目标串下标 j 由 3 回溯到 1 (为什么是1，下面描述)，就等于将目标串向后移动了 2 个位置
A B A C A B A B
A B A B
⬆️下面我们讲一下为什么要将目标字符串的下标 j 回溯到 1 这个位置。
在上面的例子中，我们可以知道，两个字符串在第 4 个字符处失去匹配，那么我们结合 next 数组，发现 next 数组中下标 j 对应的值为 1，即表明最后匹配成功的子串 ABA 的第一位和最后一位字符是相等的，那么我们下一次移动匹配后，跳过比对第一个字符这个过程，直接从第二个字符开始匹配。
于是保持模式串当前的下标 i 不变，将目标串的第二个字符移动到最后比对失败的字符处开始下一轮的对比，即 j = 1，这个 1 其实就是子串 ABA 的最长公共元素长度，也代表着我们可以跳过多少长度的字符的对比过程，所以 j = next[j]。
特殊场景： 讲了普通的场景，那么我们讲一下为什么我们在 next 数组中第一个位置放置的特殊标识符的值应该为 -1。
在比对过程中，当第一个字符就匹配失败时，即在 j = 0 的时候就比对失败。正常情况下我们要将模式串的下标 i 向后移动一个位置即 i++，将目标串的下标 j 就会回溯到 0，然后进行下一轮到比对，代码如下
i++;
j = 0;而如果在某一个字符处比对成功时，需要需要将 i 和 j 均向右移动一个位置，即
i++;
j++;对比上面两块代码，我们可以看到我们都需要进行 i++ 的处理，那么能否将 j++ 与 j = 0 收到一个逻辑里面呢？此时，如果我们设置 next[0] = -1 ，那么 j++ 实际上就等于 j = 0 。
如此设置，便实现了 比对成功 和 在第一位就比对失败 这两种逻辑的统一。
如何快速求 next 数组
在上面的例子中，所用到的 next 数组是我们依据最长长度数组处理而来，而最长长度数组是我们将目标串的每一个子串经过推演得来的，实际使用中肯定不能每次都手动推演，下面我们就讲解如何快速求出指定目标串的 next 数组。
比如我们拿字符串 ABBA 举例，先按照推演的方式列出该字符串的子串以及他们的前后缀：
| 子串 | 前缀 | 后缀 | 最大公共长度 |
|---|---|---|---|
| A | - | - | -，长度0 |
| AB | A | B | -，长度0 |
| ABB | A,AB | BB,B | -，长度0 |
| ABBA | A,AB,ABB | BBA,BA,A | A，长度1 |
首先，我们的最大公共长度肯定是由 长度相同 的前后缀比对相等得到的，因此我们应该考虑的是，如何从指定目标串中取出相同长度的前后缀，再去对比他们是否完全相同。
由于我们会在
next数组的第一位插入一个-1，所以最后一个子串ABBA没有比对的价值，因此在求next数组的过程中，不用考虑该子串，只需求A、AB、ABB的最大公共长度即可
我们先画出不同子串进行比对时的图例，为了方便查看，在下述例子中，将前后缀的位置进行了对换
// 子串 A
A B B A // 前缀 => A B B A // 后缀
A B B A // 后缀 A B B A // 前缀
// 子串AB
A B B A // 前缀 => A B B A // 后缀
A B B A // 后缀 A B B A // 前缀
// 子串ABB
A B B A // 前缀 => A B B A // 后缀
A B B A // 后缀 A B B A // 前缀这时候我们从下往上看，以右边前后缀对换后的图例来看，可以发现后缀保持不变，通过移动前缀中第一个字符的位置，可以实现不同子串对比的功能。
具体的比对过程可以查看 getNextList 这个方法，原理和主方法上面描述的模式串与目标串逻辑基本一直一致，差异点在于只需要设置一个 指向变量 以及 当前比对成功长度 变量。
在第一位就比对失败时，移动到下一个子串的比对，并将比对成功的长度归位0。因为我们第一个默认设置为 -1 ,所以直接 -1++ 即可，实现第一位比对失败和比对成功逻辑的统一。
在下面的代码中，大家可能会对 nextList[strIndex] = matchIndex 这句代码产生疑问，比如当前子串的长度为 3 ，在对比过程中可能会连续覆盖 1,2,3 三个位置的数据。其实不用担心，因为我们是从长子串开始对比，在长度为 3 的子串对比完成后，会接着对比长度为 2 的子串，这样 next[2] 位置上的值还会被覆盖成它该有的值。
以上内容就是KMP算法的整体逻辑，下面我们开始上代码。
代码
function getNextList(str) {
const strLength = str.length;
const nextList = [-1];
let strIndex = 0;
let matchIndex = -1;
while(strIndex < strLength) {
if (matchIndex === -1 || str[strIndex] === str[matchIndex]) {
strIndex++;
matchIndex++;
nextList[strIndex] = matchIndex;
} else {
matchIndex = nextList[matchIndex];
}
}
return nextList;
}
function strStr(haystack, needle) {
const hayLen = haystack.length;
const nedLen = needle.length;
if (!needle) {
return 0;
} if (nedLen > hayLen) {
return -1;
} else if (nedLen === hayLen) {
return haystack === needle ? 0 : -1;
} else {
const nextResult = getNextList(needle);
let hayIndex = 0;
let nedIndex = 0;
while(nedIndex < nedLen && hayIndex < hayLen) {
if (nedIndex === -1 || haystack[hayIndex] === needle[nedIndex]) {
hayIndex++;
nedIndex++;
} else {
nedIndex = nextResult[nedIndex];
}
}
if (nedIndex === nedLen) {
return hayIndex - nedLen;
}
return -1;
}
}leetcode执行结果
