KMP - 字符串查找算法

在腾讯的一次面试里，有一道题目为：如果字符串存在输入子串，则返回true。

我看了看题也没想，一把梭 ```return str.includes(substring)```。面试官: "喵喵喵,就一行？"。确实，一行就能实现，但如果没有api呢？应该怎么做？

### Brute-Force(暴力破解)
首先最简单的应该就是一个一个匹配了，子字符串每个字符去匹配主字符串，成功则匹配下一个，失败则回溯至主字符串的第二个字符，以此循环完所有的主字符串。
```js
function SubstringSearch(text, pattern) {
	var n = 0;
	var m = 0;
	var k = 0;
	while (m < text.length && n < pattern.length) {
		if (text[m] == pattern[n]) {
			m++;
			n++
		} else {
			k++;
			n = 0;
			m = k
		}
	}
	if (n == pattern.length) return true
	return false
}
```
上面的代码很简单，匹配成功则两个坐标+1继续进行匹配，不匹配则从主串的下一个坐标开始从新匹配;
它的时间复杂度为O(nm),有没有更快的算法呢 ？

### KMP (Knuth-Morris-Pratt) 
kmp算法能够利用子串的相同前缀后缀的最大长度（公共最大长）对匹配过程进行优化，从O(mn)到O(m+n)。

先从以下例子来理解

主字符串为: ```a b c x a b c d a b x a b c d a b c d a b c y```
子串为:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;```a b c d a b c y```

从第一个字符串开始匹配，```a b c```都能匹配成功,但是```d```和```x```并不能匹配成功。到这里我们来看看```d```之前的字符串。

```d```之前的```a b c```，这三个字符串都是单独的，并没有公共的字符串。那也就是说明了其实子字符串的第一个```a```可以直接到主字符串的```X```下标去匹配了。因为已经成功匹配了三次，并且前面没有公共的字符串，比如```a```，那么说明不管是第二次的```b```还是第三次```c```都不可能是```a```了，可以直接跳过，而不是回溯到```b```进行第二次匹配

继续到之前的逻辑```a```和```x```匹配不成功，那继续进行下一次匹配
```a b c x a b c d a b x a b c d a b c d a b c y```
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;```a b c d a b c y```

看上面的结构，下一次的匹配能够成功匹配6次然后在```c```和```x```中失败，让我们看看在```c```之前成功匹配的字符串里
```a b c d a b```

在上面我们能够发现有一个公共的前后缀字符串为```a b```。既然后缀为```a b```，说明其实主串```x```之前和子串的```c```之前都为```a b```，那么就可以跳过```a b```的判断直接进行```c```和```x```的判断

```a b c x a b c d a b x a b c d a b c d a b c y```
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;```a b c d a b c y```

判断后发现```c```和```x```不匹配，那就找```c```之前```ab```是否有公共子串。没有，和第一次失败的例子一样，跳过```a b```，进行```a```与```x```匹配，不成功，再后移一位进行匹配

```a b c x a b c d a b x a b c d a b c d a b c y```
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;```a b c d a b c y```

发现最后一个```y```是失败的，我们从```y```之前再去找信息。
```a b c d a b c```，在这一串字符串里能够知道有公共最长子字符串为```abc```,和前面的同理，没有必要再重新匹配```a b c```，那么就可以从```d```开始去匹配跟```y```匹配失败的字符串

```a b c x a b c d a b x a b c d a b c d a b c y```
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;```a b c d a b c y```

从```a b c```的```d```开始进行匹配,发现后续的字符串都能匹配成功,到这里整个字符串检索完毕。

从上面的例子能够发现，在每次匹配失败后，能够利用当前失败位前面字符串的公共前后缀的信息来跳过没必要的对比

接下来的工作就是怎么高效的算出前后缀是否相同。并且如果主串和子串的字符匹配错误的时候，该从哪里开始匹配字符

#### 构建子字符串索引信息

1.pattern - ```a b c d a b c a```

先从上面简单的子字符串来构建有无前后缀的信息

从第一个字符串开始，肯定是没有的，那么就为0，0代表着当前字符串前面的都无公共前后缀，所以代码可以从第二个字符串开始寻找公共前后缀。

第二个字符开始```a b```,```a```和```b```不相等，所以```b```的下标也为0，```c```,```d```也如此，到了```a b c d a```发现有一个公共前后缀，那么最后一个```a```的下标就为1

继续到后面```a b c d a b```能发现有两个前后缀，再继续能有三个。好了。到目前为止，我们的信息数组对应为

```a b c d a b c a```
```0 0 0 0 1 2 3 ?```

最后一次匹配发现```a b c d```和```a b c a```最后一个字符串不能匹配了，咋办？这时候就得利用以前的信息了，我们跳到在```d```的信息下标的前面一个，为0。然后去匹配第一字符串和最后一个字符串是否是公共前缀，是的话就为1，否则为0。开头```a```和结尾的```a```相同，下标为1，最后我们得出这样一个数组

```a b c d a b c a```
```0 0 0 0 1 2 3 1```

2.pattern - ```a a b a a b a a a```
再来一个例子

首先从第二个开始跟第一个比较，```a```与```a```相同，所以为第二个下标为1。继续第三个字符串```b```，前面没有任何公共前后缀，所以为0。接下来第四个到倒数第二个的地方能发现

```a a b a a b a a```
一共有5个相同的公共前后缀，为```a a b a a```。所以到目前为止的下标应该为
```a a b a a b a a a```
```0 1 0 1 2 3 4 5 ?```
 
到了最后一个字符串匹配，发现```a a b a a b```和``` a a b a a a```的最后一个字符串不相同啦，怎么办能。之前说过，需要利用以前的信息，所以应该跳到```b```之前的下标,为2,为2的坐标在字符串里是```b```，发现又和最后的```a```不匹配，那么再一次跳到之前的下标为1，发现```a```与```a```相同了,那么最后一个```a```的坐标就应该为```a```下的1再加1，为2

```a a b a a b a a a```
```0 1 0 1 2 3 4 5 2```

```js
computeTemporaryArray = function (nums) {
    var arr = [0];
    var j = 0;
    for (var i=1;i<nums.length;) {
        if (nums[j] == nums[i]) {
            arr[i] = ++j;
            i++
         } else {
            if (j != 0) {
                j = arr[j - 1];
            } else {
                arr[i] = 0
                i++
            }
        }
    }
    return arr
}
```
代码如上，时间复杂度为O(n)


我们能够做出跟n长度一样的数组并说明前后公共子字符串的的数量。接下来就是利用信息让字符匹配错误的时候，跳过不需要的匹配

### 利用子串信息匹配主串

有如下主串:
```a b x a b c a b c a b y```

子串:
```a b c a b y```
```0 0 0 1 2 0```

主字符串的坐标为i = 0,子串坐标为j = 0。

首先第一个字符开始匹配，直到```x```发现与```c```不匹配后,找到```c```之前```b```的下标信息为0,说明```c```之前没有公共前后缀，使j = 0重新开始匹配。```a```与```x```匹配失败，继续匹配下一个。一直到发现```a b c a b y```,```a b c a b y```的最后一个字符匹配失败，这时候，找到```y```之前的```c```的下标信息为2，说明有两个公共前后缀，可以跳过两次不必要的匹配。j = 2，并且主串是直接从后缀的```a b```开始进行而不回溯，也就是子串```a b c a b y```与主串的```a b c a b y```从```c```开始进行匹配看看是不是相同。最后结束匹配，返回成功。

```js
function KMP(text, patternText) {
    let pattern = computeTemporaryArray(patternText);
    var i = 0;
    var j = 0;
    while(i < text.length && j < pattern.length){
        if (text[i] == patternText[j]) {
            j++;
            i++;
        } else {
            if (j == 0) {
                i++
            } else {
                j = pattern[j - 1];
            }
        }
    }
    if(j == pattern.length){
        return true;
    }
    return false
}
```
整个主串的时间复杂度为o(m),而构建子串的信息为o(n)，所以整个时间能够缩短为o(m + n)

### 结尾
KMP算法利用匹配失败后的公共前后缀信息来跳过前面很多不必要的重复检查，从而从中间开始继续匹配是否对应，对于庞大字符的匹配，能够缩短巨大的时间。本质上其实构建子串的数组和整体去匹配也可以看做是一种动态规划的算法。


Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

KMP - 字符串查找算法 #11

Brute-Force(暴力破解)

KMP (Knuth-Morris-Pratt)

构建子字符串索引信息

利用子串信息匹配主串

结尾

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

KMP - 字符串查找算法 #11

Description

Brute-Force(暴力破解)

KMP (Knuth-Morris-Pratt)

构建子字符串索引信息

利用子串信息匹配主串

结尾

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions