前言

​ KMP 算法是一种字符串匹配算法，它可以在一个主串中查找一个模式串的出现位置。在实际应用中，字符串匹配是一个非常常见的问题，比如在搜索引擎中搜索关键词、在文本编辑器中查找字符串等等。

​ KMP 算法的发明者是 Donald Knuth、James H. Morris 和 Vaughan Pratt，他们在1977年发表了一篇论文《Fast Pattern Matching in Strings》，其中Donald Knuth 还是《计算机程序设计艺术》的作者。

​ 相比于暴力匹配算法的时间复杂度$O(nm)$，KMP 算法的优势在于它的时间复杂度为$O(n+m)$，其中n是文本串的长度，m是模式串的长度。此外，KMP 算法还可以处理一些特殊情况，例如模式串中存在重复的子串。

一、原理

1.1 暴力法

字符串匹配就是有两个字符串，分别是文本串s和模式串p，计算p在s中首次出现位置，未出现返回-1。

暴力法是最简单的字符串匹配算法，它的思路很简单：从主串的第一个字符开始，依次和模式串的每个字符进行比较，如果匹配成功，则继续比较下一个字符，否则从主串的下一个字符开始重新匹配。

暴力法时间复杂度$O(m\ast n)$

public int bruteForce(String s, String p) {
    
	int lenS = s.length();
	int lenP = p.length();
	if (lenS < lenP) return -1;

    for (int i = 0; i <= lenS - lenP; i++) {
    
        int pos = 0;
        while (pos < lenP) {
    
            if (s.charAt(i + pos) != p.charAt(pos)) {
    
                break;
            }
            pos++;
        }
        if (pos == lenP) return i;
    }
    return -1;
}

1.2 最长公共前后缀

以上面例子作为参考，会发现暴力法有许多冗余的比较，因为一旦未匹配上，直接从下一位重新开始比较，KMP 就是在这块做出了优化，不再是下一位，而是由一个next 数组决定跳转的数。

KMP 算法的核心思想是利用已经匹配过的信息，尽量减少模式串与主串的匹配次数。具体来说，KMP算法维护一个next数组，用于记录模式串中每个字符前面的最长公共前后缀的长度。在匹配过程中，如果当前字符匹配失败，则根据next数组的值调整模式串的位置，使得模式串尽可能地向右移动，从而减少匹配次数。

为什么是最长公共前后缀呢，其实用下面的例子可以很好理解

当在j=6处时匹配失败，那么你就会知道前6个字符匹配正确，那么如何得到下个跳转的位置呢？

• 肉眼可见首字母是a，即前缀为a，所以应该跳到下个a字符位置(i=2)

• 又发现存在和前缀ab相同的，所以更好的位置应该是下个ab的位置(i=4)

• 依次类推，看起来是寻找和前缀相同的最长字符串，跳转到对应的位置

• 实际发现跳转的位置是前缀相同的最长字符串对应的位置并不是最优解，最优解跟后缀相关，后缀后面有更多的可能

• 如果存在和前缀相同的最长字符串 t 并不是后缀，那么前缀+后1个字符 肯定不能匹配 t+后1个字符，浪费一次匹配机会，不是最优的位置

• 所以最好的位置应该是最长公共前后缀部分。以上述为例：就是 s[0:5]的后缀和p[0:5]的前缀 最长公共部分，由于两者相同，即abacab 的最长公共前后缀ab

注意：KMP算法在模式串具有重复度高的字符才能发挥强大的功力, 如果是全不相同的字符，会退化为暴力算法

二、代码实现

2.1 next数组

next数组的计算是KMP算法的关键，它的定义如下：

next[i]表示模式串中每个位置之前的最长相同前缀后缀的长度，即以第i - 1个字符结尾的子串p[0:i-1]中，既是前缀又是后缀的最长字符串的长度。

具体来说，我们可以通过递推的方式计算next数组，可以按照以下步骤进行：

1. next[0]=-1
2. 定义 i表示当前计算的位置，j表示当前位置之前的最长相同前缀后缀的长度
3. 后面的目标就是找到 p[0 : j-1] == p[i-j : i-1] 如果找到了这样的 j，那么next[i]的值就是j。 如果找不到这样的j，那么next[i]的值就是0
4. 如果 p[i] == p[j]，只要将next[i+1] = next[i] + 1就可以，而 j 是前一个最长相同前缀后缀的长度也就是next[i], 即next[++i] = ++j
5. 如果p[i] != p[j]，需要将 j 回溯到之前的位置next[j]

public static int[] getNext(String pattern) {
    
    int[] next = new int[pattern.length()];
    next[0] = -1;
    int i = 0, j = -1; // j为当前已经匹配的前缀的最长公共前后缀的长度
    while (i < pattern.length() - 1) {
    
        if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
    
            next[++i] = ++j; // 长度加1，并且将指针移向下一位
        } else {
    
            j = next[j]; // 回溯
        }
    }
    return next;
}

2.2 可视化next

next数组的生成是理解KMP的重中之重，可视化一下如何生成对理解KMP有很大帮助

import tkinter as tk
import time

def changeColor(canvas, rects, color):
    for rect in rects:
        canvas.itemconfig(rect, fill=color)
def visualize_next(pattern):
    next = [-1] * len(pattern)
    root = tk.Tk()
    root.title("KMP Next Visualization")
    canvas_width = 800
    canvas_height = 600
    canvas = tk.Canvas(root, width=canvas_width, height=canvas_height)
    canvas.pack()
    block_width = 50
    block_height = 50
    x_margin = 50
    y_margin = 50
    nextbox = []
    pbox = []


    x = x_margin
    y = y_margin
    canvas.create_text(x-block_width/2, y+block_height/2, text="索引", font=("Arial", 16))
    for i in range(len(pattern)):
        canvas.create_rectangle(x, y, x+block_width, y+block_height, outline="black")
        canvas.create_text(x+block_width/2, y+block_height/2, text=str(i), font=("Arial", 16))
        x += block_width

    x = x_margin
    y += block_height
    canvas.create_text(x-block_width/2, y+block_height/2, text="p", font=("Arial", 16))
    for i in range(len(pattern)):
        pbox.append(canvas.create_rectangle(x, y, x+block_width, y+block_height, outline="black"))
        canvas.create_text(x+block_width/2, y+block_height/2, text=str(pattern[i]), font=("Arial", 16))
        x += block_width

    x = x_margin
    y += block_height
    canvas.create_text(x-block_width/2, y+block_height/2, text="Next", font=("Arial", 16))

    for i in range(len(pattern)):
        canvas.create_rectangle(x, y, x+block_width, y+block_height, outline="black")
        nextbox.append(canvas.create_text(x+block_width/2, y+block_height/2, text="", font=("Arial", 16)))
        x += block_width
    
    i = 0
    j = -1
    x = x_margin
    y += block_height
    i_rect = canvas.create_rectangle(x, y, x+block_width, y+block_height, fill="red")
    i_text = canvas.create_text(x+block_width/2, y+block_height/2, text=str("i"), font=("Arial", 16))
    y += block_height
    j_rect = canvas.create_rectangle(x - block_width, y, x, y+block_height, fill="blue")
    j_text = canvas.create_text(x- block_width/2, y+block_height/2, text=str("j"), font=("Arial", 16))

    canvas.itemconfig(nextbox[0], text=str("-1"))
    time.sleep(1)
    while i < len(pattern) - 1:
        changeColor(canvas, pbox, '')
        if j == -1 or pattern[i] == pattern[j]:
            i += 1
            j += 1
            canvas.move(i_rect, block_width, 0)
            canvas.move(i_text, block_width, 0)
            canvas.move(j_rect, block_width, 0)
            canvas.move(j_text, block_width, 0)
            canvas.itemconfig(nextbox[i], text=str(j))
            changeColor(canvas, pbox[0:j], 'blue')
            changeColor(canvas, pbox[i-j:i], 'red')
            canvas.update()
            time.sleep(1)
        else:
            tmp = j
            j = next[j]
            canvas.move(j_rect, (j - tmp)*block_width, 0)
            canvas.move(j_text, (j - tmp)*block_width, 0)

            canvas.update()
            time.sleep(1)
    root.mainloop()

if __name__ == "__main__":
    pattern = "abacabb"
    visualize_next(pattern)

2.3 KMP

改造下暴力算法:

public static int kmp(String s, String p) {
    
    int[] next = getNext(p);

    int lenS = s.length();
    int lenP = p.length();
    if (lenS < lenP) return -1;
    int i = 0;

    while (i <= lenS - lenP) {
    
        int pos = 0;
        while (pos < lenP) {
    
            if (s.charAt(i + pos) != p.charAt(pos)) {
    
                break;
            }
            pos++;
        }
        if (pos == lenP) return i;
        i += pos - next[pos];
    }
    return -1;
}

三、总结

3.1 优点

• KMP算法的时间复杂度为O(n+m)，其中n为主串长度，m为模式串长度。相比于暴力法的O(n*m)，KMP算法的效率更高。

• Python中的re模块是用C语言实现的，底层使用了KMP算法来进行正则表达式的匹配。正则表达式通常用于处理大量文本数据，因此对于正则表达式匹配的性能要求比较高。使用KMP算法可以提高正则表达式匹配的效率，因此在Python中的re模块中使用KMP算法来实现正则表达式匹配，可以提高程序的性能。

• KMP算法可以处理模式串中存在重复子串的情况，而其他字符串匹配算法则无法处理。

3.2 缺点

• 在字符串小的情况下应用不多，在 JDK 中的 String.indexOf 方法使用了一种基于暴力匹配的算法，而不是KMP。这是因为在实际应用中，字符串的长度通常不会很长，而且KMP算法需要额外的空间来存储前缀表，这会增加内存的使用量。因此，对于较短的字符串，使用暴力匹配算法可以获得更好的性能。 另外，JDK中的String.indexOf方法还使用了一些优化技巧，例如在匹配失败时跳过一定长度的字符，以减少比较的次数。这些优化技巧可以在大多数情况下提高算法的效率，从而满足实际应用的需求。
• KMP 算法的局限性在于它需要预处理模式串，这个预处理的时间复杂度为$O(m)$，因此在模式串很长的情况下，KMP 算法的效率可能会受到影响。
• KMP 算法只能用于匹配单个模式串，无法处理多个模式串的匹配问题。

参考

1. （原创）详解KMP算法
2. KMP Algorithm for Pattern Searching