KMP 算法

博主： Mashiro
发布时间：2023 年 02 月 09 日
592 次浏览
暂无评论
4423字数
分类：算法

# KMP 算法

## 简介

Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。——引自维基
在模式匹配问题中，KMP算法比Manacher算法更具普适性，Manacher算法只适用于 `回文串` 问题，较为局限。

## 例题引入

以 [LeetCode 28. 找出字符串中第一个匹配项的下标](https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/) 为例
题目给出一个字符串 `text` 和一个模式串 `pattern`，要求返回 `text` 中第一次匹配模式串的下标
例：text = ababc, pattern = abc, answer = 2

### 暴力解法

```java
public static int strStr(String text, String pattern) {
	int textLen = text.length();
	int patternLen = pattern.length();
	for (int i = 0; i < textLen - patternLen; i++) {
		boolean flag = true;
		for (int j = 0; j < patternLen; j++) {
			if (pattern.charAt(j) != text.charAt(i + j)) {
				flag = false;
				break;
			}
		}
		if (flag) {
			return i;
		}
	}
	return -1;
}
```

很容易看出时间复杂度为 O(m * n)
![KMP-1.gif](https://cdn2.feczine.cn/2023/02/08/63e3baf1e96b8.gif)
原因是每次内循环匹配失败后，j 总是回溯到0，重新匹配
而`匹配失败`的意思是当前字符不匹配，而当前字符`之前`的子串是匹配的
而KMP算法就是利用了这一特性，使得复杂度降低到了 O(m + n)

### KMP算法

#### 最长公共前后缀

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
例如：
`aabaa` 的前缀是 `aaba` 后缀是 `abaa`
而 **公共** 则要求前后缀相等
则 `aabaa` 的最长公共前后缀是 `aa`

#### next数组

我们用 i 表示字符串的结尾，j 表示该字符串前缀的结尾

> 构造next数组的过程其实是 pattern**自我匹配** 的过程

pattern = `aabaaf`

```
"a" 无意义，不满足前后缀定义，i 从 1 开始
"aa"     i = 1, j = 1, next[1] = 1
"aab"    i = 2, j = 0, next[2] = 0
"aaba"   i = 3, j = 1, next[3] = 1
"aabaa"  i = 4, j = 2, next[4] = 2
"aabaaf" i = 5, j = 0, next[5] = 0
```

代码实现

```java
int patternLen = pattern.length();
    int[] next = new int[patternLen];
//    构造next[]
//    i 指向 子串的最后
//    j 指向 前缀的最后
    for (int i = 1, j = 0; i < patternLen; i++) {
//        不匹配, j 为 长度-1 子串的结果
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
//        长度为 i 的子串的最长公共前后缀的长度为 j, 索引为 j - 1
//        即存放公共前后缀之后的字符的索引
        next[i] = j;
    }
```

#### 匹配搜索

![KMP-2.gif](https://cdn2.feczine.cn/2023/02/09/63e3e69548f13.gif)

```java
int textLen = text.length();
//    search
//    i 指向 text
//    j 指向 pattern
    for (int i = 0, j = 0; i < textLen; i++) {
//        不匹配, j 为 长度-1 子串的结果,
//        直到匹配, 边界情况为 j = 0
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
//        匹配, j 后移
//        除前面全不匹配外，均匹配
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        if (j == patternLen) {
            return i - patternLen + 1;
        }
    }
```

#### 实现

```java
public static int kmp(String text, String pattern) {
        int textLen = text.length();
        int patternLen = pattern.length();
        int[] next = new int[patternLen];
//        构造next[]
//        i 指向 子串的最后
//        j 指向 前缀的最后
        for (int i = 1, j = 0; i < patternLen; i++) {
//            不匹配, j 为 长度-1 子串的结果
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
//            长度为 i 的子串的最长公共前后缀的长度为 j, 索引为 j - 1
//            即存放公共前后缀之后的字符的索引
            next[i] = j;
        }
//        search
//        i 指向 text
//        j 指向 pattern
        for (int i = 0, j = 0; i < textLen; i++) {
//            不匹配, j 为 长度-1 子串的结果,
//            直到匹配, 边界情况为 j = 0
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
//            匹配, j 后移
//            除前面全不匹配外，均匹配
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == patternLen) {
                return i - patternLen + 1;
            }
        }
        return -1;
    }
```

</br></br>
参考资料：
1.[KMP 算法详解](https://zhuanlan.zhihu.com/p/83334559)
2.[代码随想录](https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html)
3.【喵的算法课】KMP算法 av808837277
4.[【宫水三叶】简单题学 KMP 算法](https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/)
5.[海纳的知乎回答](https://www.zhihu.com/question/21923021/answer/281346746)
6.[Wiki](https://zh.wikipedia.org/wiki/KMP%E7%AE%97%E6%B3%95)

最后修改：2023 年 02 月 09 日