Python 比赛实战：字符串子串匹配（内置方法、正则与手速版 KMP）

2026-09-07 00:00    #Python   #算法竞赛   #字符串   #KMP  

在算法比赛（ACM / Codeforces / LeetCode / 蓝桥杯）中，面对字符串匹配问题，核心目标是在最短时间内快速验证思路。

不同的场景下，盲目手写标准 KMP 往往不是最优解。本文总结在比赛中使用 Python 进行子串查找与验证的高效策略。

1. 场景一：仅验证存在 / 找首个出现位置

如果在比赛中只需要知道模式串 p 是否在文本串 s 中出现，或者只需要第一次出现的位置：

绝不要手写 KMP，直接使用 Python 内置方法

Python 内置的 in 和 s.find() 是由 C 底层（CPython Fastsearch，结合了 Boyer-Moore-Horspool 与哈希优化）实现的，运行效率极高，且 0 错码风险。

1# 1. 验证是否存在
2if p in s:
3    print("Found!")
4
5# 2. 获取第一次出现的起始下标（未找到返回 -1）
6pos = s.find(p)

2. 场景二：极速查找所有子串位置（含重叠匹配）

如果要求找出模式串 p 在文本串 s 中的所有出现位置（含重叠匹配），有以下两种高手速方案：

2.1 方案 A：s.find() 循环（5 行代码）

利用 s.find(sub, start) 移动 start 指针不断向后寻找：

1def find_all(s: str, p: str) -> list[int]:
2    if not p: return []
3    ans, pos = [], s.find(p)
4    while pos != -1:
5        ans.append(pos)
6        pos = s.find(p, pos + 1)  # pos + 1 允许重叠；若不允许写 pos + len(p)
7    return ans

2.2 方案 B：正则前瞻断言（一行代码）

利用 re 模块与零宽正预测先行断言 (?=...) 实现重叠匹配：

1import re
2
3ans = [m.start() for m in re.finditer(f'(?={re.escape(pattern)})', text)]

测试验证

1text = "abababa"
2pattern = "aba"
3
4ans = [m.start() for m in re.finditer(f'(?={re.escape(pattern)})', text)]
5print(ans)  # [0, 2, 4]

原理

  1. re.escape(pattern)：防止模式串中包含 .、*、? 等正则特殊字符。
  2. (?=...)：只匹配位置而不消耗文本字符，匹配完后能从下一个字符继续，实现重叠匹配。
  3. m.start()：提取匹配到的起始下标。

如果不允许重叠匹配：

1ans = [m.start() for m in re.finditer(re.escape(pattern), text)]  # [0, 4]

3. 场景三：严格 O(N+M)O(N+M) 复杂度（手速版 KMP）

当数据量极大（N≥106N \ge 10^6）且存在针对暴力的构造数据，或需要利用 π\pi 数组的周期/循环节性质时，手写 KMP 是必要的。

比赛中采用高度压缩的手速版 KMP：

 1def kmp_all(s: str, p: str) -> list[int]:
 2    if not p: return []
 3    n, m = len(s), len(p)
 4    
 5    # 1. 快速构造 pi 数组
 6    pi, j = [0] * m, 0
 7    for i in range(1, m):
 8        while j > 0 and p[i] != p[j]: j = pi[j - 1]
 9        if p[i] == p[j]: j += 1
10        pi[i] = j
11
12    # 2. 文本匹配
13    ans, j = [], 0
14    for i in range(n):
15        while j > 0 and s[i] != p[j]: j = pi[j - 1]
16        if s[i] == p[j]: j += 1
17        if j == m:
18            ans.append(i - m + 1)
19            j = pi[j - 1]
20            
21    return ans

敲写技巧

4. 比赛实战决策表

比赛需求推荐方案核心优势
仅需判断是否存在 / 找首个位置p in s 或 s.find(p)C 底层实现，极速且 0 错码风险
需要找所有位置 (重叠/非重叠)s.find(p, pos + 1) 循环5 行代码，手速极快
追求代码极短 (一行搞定)re.finditer(f'(?={re.escape(p)})', s)一行包含重叠匹配
存在极端构造数据 / 需周期性质15 行手速版 KMP严格 O(N+M)O(N+M)，防止被卡 TLE