命令行与文本处理 / 系统课时

公共前缀提取

公共前缀提取

学习目标

  • 识别多个分支中的公共前缀。
  • 会把重复文本移到分组外。
  • 理解提取公共部分对维护性的帮助。
  • 能验证重构前后匹配集合一致。

问题背景或应用场景

多个分支共享较长前缀时,重复书写会让模式变长,也容易在修改时漏掉某个分支。例如 prepaid、preview 和 prevent 都以 pre 开头,可以将公共前缀提取到分组之外。

核心原理

  1. 公共前缀是所有候选分支开头完全相同的部分。
  2. 提取公共前缀后,分组中只保留变化部分。
  3. 重构后的模式应与原模式匹配相同的文本集合。
  4. 公共后缀也可以用同样思路提取。
  5. 提取过度会产生难读的碎片,应在简洁与可读性之间平衡。

模式 prepaid|preview|prevent 可以重构为 pre(?:paid|view|vent)。两者匹配集合相同,但后者减少了公共前缀的重复。

基础用法

本课涉及的核心写法如下:

text
prepaid|preview|prevent
pre(?:paid|view|vent)
cat|car|can
ca(?:t|r|n)

重构分支后必须使用正例和反例验证,确保没有错误移动字符,也没有扩大或缩小合法范围。

完整可运行示例

将代码保存为:

text
common_prefix.py
python
import re

original = r"prepaid|preview|prevent"
factored = r"pre(?:paid|view|vent)"

samples = ["prepaid", "preview", "prevent", "prepare", "paid"]

for text in samples:
    original_match = re.fullmatch(original, text) is not None
    factored_match = re.fullmatch(factored, text) is not None
    print(
        f"{text}: 原模式={original_match}, "
        f"提取前缀={factored_match}"
    )

animal_original = r"cat|car|can"
animal_factored = r"ca(?:t|r|n)"
print(f"cat 等价:{re.fullmatch(animal_factored, 'cat') is not None}")
print(f"cap 等价:{re.fullmatch(animal_factored, 'cap') is not None}")

运行命令:

bash
python common_prefix.py

预期输出

text
prepaid: 原模式=True, 提取前缀=True
preview: 原模式=True, 提取前缀=True
prevent: 原模式=True, 提取前缀=True
prepare: 原模式=False, 提取前缀=False
paid: 原模式=False, 提取前缀=False
cat 等价:True
cap 等价:False

Tips

  • 只提取所有分支真正共有的字符。
  • 重构后应同时测试所有原合法候选。
  • 还要加入相似但非法的反例。
  • 过度压缩可能降低可读性,不必追求最短字符数。

常见错误

1. 提取了并非所有分支共有的字符

公共前缀必须在每个分支中完全相同,否则会改变匹配集合。

2. 只验证一个候选

重构后必须覆盖所有分支和相似反例。

3. 为了短而过度拆分

极端压缩会让模式难以阅读,维护性比字符数更重要。

本课练习

  1. 将 cat|car|can 重构为公共前缀形式。
  2. 将 service-start|service-stop|service-restart 提取公共前缀。
  3. 为重构前后准备正例和反例。
  4. 尝试提取一个公共后缀并说明结构。
按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

公共前缀提取

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通