【模板】KMP

GitHub跳转原题关系图返回列表

用前缀函数在线性时间输出所有匹配位置，并给出模式串每个前缀的最长 border。

启发题

启发记录： KMP 模板题，前缀函数（pi 数组）和匹配回退的定式

OJ: luogu

题目 ID: P3375

难度:普及/提高-

标签:KMP前缀函数字符串python

日期: 2026-07-16 19:57

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

输出模式串在文本中的所有出现位置，以及模式串每个前缀的最长真前后缀长度。

思路

prefix[i] 表示 pattern[:i+1] 的最长 border 长度。计算新位置时，若字符失配，就令 j = prefix[j-1]，沿 border 链退到下一个可能长度；每次指针的增加和回退总量都是线性的。

匹配文本时使用相同回退规则。j == m 表示找到一次完整匹配，输出位置后退到模式串的次长 border，从而允许重叠匹配。

Python 知识

  • 字符串按 bytes 处理时，下标访问直接得到整数，百万字符扫描更省内存。
  • array("i") 只用 4 字节保存一个前缀函数值。
  • 匹配位置先写入 bytearray，前缀数组再按 8192 个一块输出，避免创建百万个字符串对象。
  • enumerate(text) 同时取得文本下标和字符。

代码

python
import sys
from array import array


text, pattern = sys.stdin.buffer.read().split()
m = len(pattern)
prefix = array("i", [0]) * m

j = 0
for i in range(1, m):
    while j and pattern[i] != pattern[j]:
        j = prefix[j - 1]
    if pattern[i] == pattern[j]:
        j += 1
    prefix[i] = j

matches = bytearray()
j = 0
for i, character in enumerate(text):
    while j and character != pattern[j]:
        j = prefix[j - 1]
    if character == pattern[j]:
        j += 1
    if j == m:
        matches.extend(f"{i - m + 2}\n".encode())
        j = prefix[j - 1]

write = sys.stdout.buffer.write
write(matches)
for start in range(0, m, 8192):
    block = " ".join(map(str, prefix[start:start + 8192])).encode()
    write((b"" if start == 0 else b" ") + block)
write(b"\n")
python
import sys


s1, s2 = [x.decode() for x in sys.stdin.buffer.read().split()]

def find_all(s1,s2):
    if not s2 :
        return []
    ans ,pos = [],s1.find(s2)
    while pos != -1:
        ans.append(pos+1) # 位置从1开始
        pos = s1.find(s2,pos+1)
    return ans


def build_prefix(s):
    if not s:
        return []
    pi = [0] * len(s)
    j = 0
    for i in range(1,len(s)):
        while j != 0 and s[i] != s[j]:
            j = pi[j-1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j

    return pi

def solve():
    ans = find_all(s1, s2)
    if ans:
        print(*ans, sep="\n")
    pi = build_prefix(s2)
    if pi:
        print(*pi, sep=" ")
    print(*pi, sep=" ")
    


if __name__ == "__main__":
    solve()

main1.py 用 str.find 做匹配，逻辑正确但有两个点会 TLE（全 A 的长串反复调用 find 退化到 O(n2)O(n^2)）。

纯 Python 实现的 KMP：

python
import sys


s1, s2 = [x.decode() for x in sys.stdin.buffer.read().split()]

def build_prefix(s):
    if not s:
        return []
    pi = [0] * len(s)
    j = 0
    for i in range(1,len(s)):
        while j != 0 and s[i] != s[j]:
            j = pi[j-1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j

    return pi

def kmp(s1,s2,prefix = []):
    if not prefix:
        prefix = build_prefix(s2)
    equal_pos = []
    j = 0
    for i in range(0,len(s1)):
        while j !=0 and s1[i] != s2[j]:
            j = prefix[j-1]
        if s1[i] == s2[j]:
            j += 1
        if j == len(s2):
            equal_pos.append(i - len(s2) +1)
            j = prefix[j-1]

    return equal_pos


def solve():
    pi = build_prefix(s2)
    pos = kmp(s1,s2,pi)
    pos2 = map(lambda x: x+1,pos)
    if pos:
        print(*(pos2),  sep="\n")
    print(*pi, sep=" ")
    


if __name__ == "__main__":
    solve()

main-kmp.py 用标准 KMP 算法做匹配，代码可读性好，但未做内存优化，百万字符下 Python 对象开销比 main.py 大。

复杂度

做法 时间 空间
main.py（KMP + array + 缓冲） O(∣text∣+∣pattern∣)O(|text|+|pattern|) O(∣pattern∣)O(|pattern|) 加输出缓冲
main-kmp.py（纯 Python KMP） O(∣text∣+∣pattern∣)O(|text|+|pattern|) O(∣text∣+∣pattern∣)O(|text|+|pattern|)
main1.py（str.find） O(n2)O(n^2) 退化（2 TLE） O(1)O(1)

总结

KMP 的核心不是背循环，而是理解 prefix[j-1] 给出了失配后仍可能匹配的最长前缀。