数据结构与算法 / 系统课时

字符串匹配问题

字符串匹配问题

字符串匹配研究的是:给定文本串与模式串,判断模式是否出现、出现在哪里,以及相关前缀和后缀如何描述。掌握这些术语后,后续学习朴素匹配、KMP、Rabin-Karp 等算法时,才能准确理解算法输入、输出与优化目标。

学习目标

  • 能用文本串、模式串和匹配位置形式化描述字符串匹配问题。
  • 能区分全串匹配、首次出现与全部匹配位置。
  • 能识别前缀、后缀、真前缀、真后缀与边界串。

问题定义与基本术语

设文本串为 T,长度为 n;模式串为 P,长度为 m。当某个起始下标 s 满足 T[s:s+m] == P 时,就称模式串在文本串的下标 s 处发生一次匹配。

术语 含义 示例
单模式匹配 在一个文本串中查找一个固定模式串 在 abababa 中查找 aba
首次匹配 只返回最靠左的一个匹配位置 返回下标 0
全部匹配位置 返回模式串出现的所有起始下标 返回下标 0、2、4
全串匹配 模式串与整个文本串长度相同且内容相等 abc 与 abc
未匹配 不存在满足条件的起始下标 在 abc 中查找 bd

为避免术语混淆,本课把“全匹配”理解为模式覆盖整个文本;若要表达查找所有出现位置,则使用“全部匹配位置”。

字符串匹配基本关系图

前缀、后缀与边界串

字符串 S 的前缀是从开头截取的连续片段,后缀是到结尾结束的连续片段。若片段不等于 S 本身,则称为真前缀或真后缀。

以 ababa 为例:

  • 真前缀为 a、ab、aba、abab。
  • 真后缀为 a、ba、aba、baba。
  • 同时是真前缀和真后缀的字符串称为边界串,因此 a 和 aba 都是 ababa 的边界串。

边界串描述了模式内部的重复结构。后续算法会利用这些重复信息,在失配后跳过已经确定不可能成功的位置。

最小可运行示例

下面的 Python 程序同时演示全部匹配位置、全串匹配、真前缀和真后缀。程序把空模式串视为非法输入,避免不同系统对空串语义的差异。

python
def find_all(text: str, pattern: str) -> list[int]:
    if pattern == "":
        raise ValueError("pattern must not be empty")

    positions = []
    limit = len(text) - len(pattern) + 1
    for start in range(max(0, limit)):
        if text[start:start + len(pattern)] == pattern:
            positions.append(start)
    return positions

def is_full_match(text: str, pattern: str) -> bool:
    return text == pattern

def proper_prefixes(value: str) -> list[str]:
    return [value[:end] for end in range(1, len(value))]

def proper_suffixes(value: str) -> list[str]:
    return [value[start:] for start in range(1, len(value))]

def main() -> None:
    text = "abababa"
    pattern = "aba"
    sample = "ababa"

    print("全部匹配位置:", find_all(text, pattern))
    print("是否全串匹配:", is_full_match(pattern, "aba"))
    print("真前缀:", proper_prefixes(sample))
    print("真后缀:", proper_suffixes(sample))

if __name__ == "__main__":
    main()

将代码保存为 string_matching_terms.py,再运行:

bash
python string_matching_terms.py

预期输出

text
全部匹配位置: [0, 2, 4]
是否全串匹配: True
真前缀: ['a', 'ab', 'aba', 'abab']
真后缀: ['a', 'ba', 'aba', 'baba']

边界条件与易混淆点

当 m > n 时,模式串不可能在文本串中出现;当 m == n 时,最多只有下标 0 一个候选位置。重叠匹配不能被遗漏,例如 aba 在 abababa 中的三个匹配区间彼此重叠。

字符串下标通常从 0 开始,但题目也可能要求从 1 开始输出。实现前应确认下标约定,并明确是否允许空模式串。不同库对空模式串的处理并不完全一致。

本课练习

  1. 给定文本串 aaaa 和模式串 aa,写出全部匹配位置,并说明为什么不能在找到第一个匹配后直接跳过两个字符。
  2. 列出字符串 abcab 的全部真前缀、真后缀和边界串。
  3. 设计三个测试用例,分别覆盖模式比文本长、模式与文本完全相同、模式完全不存在三种情况,并写出预期结果。

本课总结

  • 字符串匹配的核心输出是满足 T[s:s+m] == P 的起始下标 s。
  • 全串匹配、首次匹配和全部匹配位置表达的是不同需求。
  • 前缀、后缀与边界串揭示模式内部的重复结构,是后续高效算法的重要基础。

下一课预告

下一课将学习“朴素字符串匹配”,通过逐个对齐模式串实现查找,并分析重复比较为什么会带来较高的时间成本。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

字符串匹配问题

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

登录哪都通