• 前言
• 朴素子字符串查找算法
• KMP 算法的基本思想
• 基于 DFA 的 KMP 实现
• 基于 PMT 的 KMP 实现
• 历史渊源 & DFA & PMT
• 结语
• 参考链接

前言1。

如下图（来自 - 如何更好地理解和掌握 KMP 算法? - 海纳的回答 - 知乎）：

这样，我们在匹配失败时就可以根据 next 调整模式指针，具体查找逻辑就为：

def kmp_search(txt: str, pat: str) -> int:
    txt_len, pat_len = len(txt), len(pat)

    i = j = 0

    while i < txt_len and j < pat_len:
        if j == -1 or txt[i] == pat[j]:
            i += 1
            j += 1
        else:
            j = next[j]

    if j == pat_len:
        return i - pat_len

    return -1

next[0] = -1, 当 txt[i] != pat[0] 时，j 的值会变为 -1，这时就可以进入另一个分支让 i + 1 并让 j 归 0

现在的问题是，如何构建这个 next 数组，很巧的是，这个构建过程也是有规律的，由于值 PMT[j] 表示的是串 pat[0:j + 1] 中的最大公共长度， 那么，值 next[j] 表示的是串 pat[0:j] 中的最大公共长度。

假如该值等于 2，那么就是说存在类似 AB...AB 的情况：

0           j
A B ... A B ?

如果，这个时候，满足 pat[next[j]] = pat[j] 这个条件，比如说是字符 C，那么，就变成了 ABC...ABC 这个情况，即：

0             j
A B C ... A B C
    2
    |
pat[next[j]]

可以发现：

• 当 pat[next[j]] = pat[j] 时，值 next[j + 1] 也就等于 next[next[j]] + 1

如果不满足，那么，也就是说，最大公共长度还位于 更短 的串中，也就是在 pat[0:next[j]] 的内部：

0             j
A B D ... A B A
--- 2
 |
pat[0:next[j]]

此时，便可以重复前面的过程，判断 pat[next[next[j]]] = pat[j] 是否成立，这里恰好一样，值 next[next[j]] 为 0，因此 next[j + 1] 的值就为 0 + 1。

构造 next 数组时便可以重复上述过程，直到 next[j] = pat[j] 或 j = 0 为止：

def make_next(pat):
    i, j, pat_len, next = 0, -1, len(pat), [-1]

    while i < pat_len:
        if j == -1 or pat[i] == pat[j]:
            i += 1
            j += 1
            next.append(j)
        else:
            j = next[j]

    return next

完整实现：

def kmp_search(txt: str, pat: str) -> str:
    txt_len, pat_len = len(txt), len(pat)

    def make_next():
        i, j, next = 0, -1, [-1]

        while i < pat_len:
            if j == -1 or pat[i] == pat[j]:
                i += 1
                j += 1
                next.append(j)
            else:
                j = next[j]

        return next

    i, j, next = 0, 0, make_next()

    while i < txt_len and j < pat_len:
        if j == -1 or txt[i] == pat[j]:
            i += 1
            j += 1
        else:
            j = next[j]

    if j == pat_len:
        return i - pat_len

    return -1

历史渊源 & DFA & PMT另一个树的子树，难度是简单，我用 DFS 暴力 AC 后去看了一下题解……

评论区的一个评论是这样的：竟然用一个题涵盖 KMP DFS HASH 埃氏筛选法 收藏从未停止 学习从未开始。

而我的心情是这样的：（￣︶￣）↗ => (⊙_⊙)？

讲道理，这样的题基本没见过几个，恰好又用了 Copy 过几次的 KMP，所以就来研究了一下。

感觉还可以 (～￣▽￣)～

参考链接从 DFA 角度理解 KMP 算法_{fpga开发DC的陋室}-CSDN博客

KMP 字符串查找算法的两种实现 - 知地 | Donche

如何更好地理解和掌握 KMP 算法? - 知乎

Footnotes

¹ 这里的 -1 和 next 数组都是为了编程方便，也可以选择不这样做