跳到主要内容
预计阅读 25 分钟

文本里的侦探 —— 字符串匹配算法

你每天按Ctrl+F搜索文本、搜索引擎检索网页、杀毒软件扫描病毒特征码——这些背后都是字符串匹配算法在工作。从最朴素的逐字比对到巧妙的模式跳跃，字符串匹配是一门充满智慧的技术。

📋 开篇自测：你已经知道多少？

  1. 在一本10万字的小说中查找一个10个字的句子，最笨的方法要比较多少次？有没有更快的方法？
  2. KMP算法的核心思想是什么？它为什么比暴力匹配快？
  3. 你知道Ctrl+F搜索文本时，编辑器用的是什么算法吗？

一、问题的定义——我们到底在做什么

字符串匹配问题可以这样描述：

  • 文本串（Text）： 一段很长的文本，比如一篇文章
  • 模式串（Pattern）： 你要查找的内容，比如一个关键词
  • 目标： 在文本串中找到模式串出现的位置
text = "大家好我是数据结构与算法的学习者大家好"
pattern = "数据结构"
# 期望输出：模式串在位置4出现

这看起来很简单——Python一行就能搞定：

print(text.find(pattern))  # 4

但你有没有想过，find()背后是怎么工作的？如果文本有10GB，模式串有1000个字符呢？不同的算法，性能差距可能是几十倍甚至上百倍。

二、暴力匹配——最直接的方法

思路

把模式串放在文本串的每一个位置上试一试，逐字符比较。匹配不上就往后挪一位，从头再来。

就像你拿着一把尺子在一根长绳上滑动，每个位置都量一下尺寸是否吻合。

def brute_force_match(text, pattern):
    """暴力匹配"""
    n, m = len(text), len(pattern)
    positions = []
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            positions.append(i)
    return positions

text = "ABABABABCABABD"
pattern = "ABABC"
print(brute_force_match(text, pattern))  # [4]

时间复杂度： 最坏 O(n * m)，其中n是文本长度，m是模式长度 空间复杂度： O(1)

当模式串是”AAAAB”而文本串是”AAAAAAAAAA…AB”这种情况时，暴力匹配会非常慢——每次都匹配到最后一个字符才发现不对，然后只后移一位重来。

🤔 想一想 在暴力匹配中，当匹配失败时，我们把模式串往后移了一位，之前匹配的信息全部丢弃了。有没有办法利用已经匹配的部分来跳过一些不必要的比较？

三、KMP算法——永不回头的智慧

核心思想

KMP算法（Knuth-Morris-Pratt）的关键洞察是：当匹配失败时，我们已经知道了文本中已经匹配过的部分是什么。利用这个信息，可以跳过一些不可能匹配的位置。

打个比方：你在一篇文章中找”ABCABD”这个词。你已经匹配了”ABCAB”，在第6个字符发现不匹配。暴力方法会退回到起点的下一位重来。但你注意到——“ABCAB”的前缀”AB”和后缀”AB”是一样的。这意味着你不需要完全从头开始，可以利用已经匹配的”AB”继续往前。

next数组（部分匹配表）

KMP的精髓在于预处理模式串，计算出一个next数组（也叫部分匹配表/前缀函数）。它记录的是：模式串的每个前缀中，最长相等前后缀的长度。

def build_next(pattern):
    """构建KMP的next数组"""
    m = len(pattern)
    next_arr = [0] * m
    j = 0  # 前缀末尾位置

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

    return next_arr

# 例子
pattern = "ABCABD"
print(build_next(pattern))
# [0, 0, 0, 1, 2, 0]
# 解读：
# A -> 0（没有真前缀等于真后缀）
# AB -> 0
# ABC -> 0
# ABCA -> 1（前缀A = 后缀A）
# ABCAB -> 2（前缀AB = 后缀AB）
# ABCABD -> 0

KMP匹配过程

def kmp_search(text, pattern):
    """KMP字符串匹配"""
    if not pattern:
        return [0]

    next_arr = build_next(pattern)
    n, m = len(text), len(pattern)
    positions = []
    j = 0  # 模式串的匹配位置

    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j - 1]  # 利用next数组跳过不必要的比较
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            positions.append(i - m + 1)
            j = next_arr[j - 1]  # 继续查找下一个匹配

    return positions

text = "ABABABABCABABD"
pattern = "ABABC"
print(kmp_search(text, pattern))  # [4]

# 测试多次匹配
text2 = "AABAABAABAAB"
pattern2 = "AABAA"
print(kmp_search(text2, pattern2))  # [0, 3, 6]

时间复杂度： O(n + m)——预处理O(m)，匹配O(n) 空间复杂度： O(m)——存储next数组

KMP最大的优点是：文本串的指针永远不会回退。 每个文本字符最多被比较两次，所以时间复杂度是严格的O(n + m)。

用一个直观的例子理解KMP

文本串：  A B A B A B A B C
模式串：  A B A B C
                    ↑ 不匹配！

暴力法：模式串后移1位
文本串：  A B A B A B A B C
模式串：    A B A B C
          ↑ 从头开始比较

KMP法：利用已匹配的"ABAB"中AB=AB的信息，直接跳过
文本串：  A B A B A B A B C
模式串：      A B A B C
              ↑↑ 已知匹配，从这里继续

KMP跳过了暴力法中肯定不会成功的那些位置，省去了大量无用功。

四、BM算法——从后往前的逆向思维

核心思想

Boyer-Moore（BM）算法从模式串的末尾开始比较（从右往左），利用两个启发式规则来决定跳过多少位。

为什么从后往前？因为如果末尾就不匹配，我们可以一次跳过很多字符。

BM有两条规则：

坏字符规则： 当某个字符不匹配时，看这个”坏字符”在模式串中最后出现的位置，据此计算跳跃距离。

好后缀规则： 如果模式串的某个后缀已经匹配了，看这个后缀在模式串的其他地方有没有出现过。

def bm_bad_char_only(text, pattern):
    """BM算法简化版：仅使用坏字符规则，未实现好后缀规则。
    匹配成功时只移动1位（完整BM会利用好后缀规则跳更远）。"""
    n, m = len(text), len(pattern)
    if m == 0:
        return [0]

    # 构建坏字符表：每个字符在模式串中最后出现的位置
    bad_char = {}
    for i in range(m):
        bad_char[pattern[i]] = i

    positions = []
    i = 0  # 文本串中的对齐位置
    while i <= n - m:
        j = m - 1  # 从模式串末尾开始比较
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        if j < 0:
            positions.append(i)
            # 注意：这里用了简化策略，找到匹配后只移动1位。
            # 完整的BM算法会利用"好后缀规则"计算更大的跳跃距离，
            # 即跳到模式串中下一个能与已匹配后缀对齐的位置，
            # 从而避免逐位移动。实际工程实现（如grep）会同时
            # 使用坏字符规则和好后缀规则，取两者中更大的跳跃值。
            i += 1
        else:
            # 坏字符：text[i+j]
            bad_char_pos = bad_char.get(text[i + j], -1)
            shift = j - bad_char_pos
            i += max(1, shift)

    return positions

text = "HERE IS A SIMPLE EXAMPLE"
pattern = "EXAMPLE"
print(bm_bad_char_only(text, pattern))  # [17]

时间复杂度： 平均O(n/m)——在实际文本中通常比KMP更快 最坏情况： O(n * m)

BM算法在实际中往往是最快的字符串匹配算法。许多文本编辑器的”查找”功能（包括grep命令）都是基于BM或其变体实现的。

为什么BM实际更快？因为在普通文本中，不匹配的情况远多于匹配。当末尾字符不匹配时，BM可以一次跳过多个字符，跳跃距离最多可达模式串的长度m。

🤔 想一想 如果模式串很短（比如只有2-3个字符），BM算法的优势还明显吗？为什么？

五、Rabin-Karp算法——用哈希加速比较

核心思想

Rabin-Karp算法用一个巧妙的方式避免了逐字符比较：先计算模式串的哈希值，然后滑动窗口计算文本子串的哈希值，只有当哈希值相同时才逐字符验证。

关键技巧是滚动哈希——当窗口右移一位时，不需要重新计算整个子串的哈希值，只需要减去最左边字符的贡献、加上最右边字符的贡献。

def rabin_karp(text, pattern):
    """Rabin-Karp字符串匹配"""
    n, m = len(text), len(pattern)
    if m > n:
        return []

    base = 256  # 字符集大小
    mod = 101   # 取模用的质数
    positions = []

    # 计算模式串和第一个窗口的哈希值
    pattern_hash = 0
    window_hash = 0
    h = 1  # base^(m-1) % mod
    for i in range(m - 1):
        h = (h * base) % mod

    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod

    # 滑动窗口
    for i in range(n - m + 1):
        if pattern_hash == window_hash:
            # 哈希匹配，逐字符验证（防止哈希冲突导致的误判）
            if text[i:i + m] == pattern:
                positions.append(i)
        if i < n - m:
            # 滚动哈希：去掉最左字符，加上最右字符
            window_hash = ((window_hash - ord(text[i]) * h) * base
                          + ord(text[i + m])) % mod
            if window_hash < 0:
                window_hash += mod

    return positions

text = "ABABABABCABABD"
pattern = "ABABC"
print(rabin_karp(text, pattern))  # [4]

时间复杂度： 平均O(n + m)，最坏O(n * m)——取决于哈希冲突的频率

Rabin-Karp的一个独特优势是可以同时搜索多个模式串——只需要把所有模式串的哈希值存在一个集合中，每个窗口位置查一次集合就行了。

六、算法对比与实际选择

算法平均时间最坏时间预处理适用场景
暴力匹配O(n*m)O(n*m)无短模式串、小数据
KMPO(n+m)O(n+m)O(m)需要严格线性时间保证
BMO(n/m)O(n*m)O(m+字符集)普通文本搜索，实际最快
Rabin-KarpO(n+m)O(n*m)O(m)多模式串匹配

实际工程中的选择

  • grep命令： 使用BM算法的变体（GNU grep使用了混合策略）
  • Python的str.find()和in： 使用自适应策略——默认采用Boyer-Moore-Horspool变体，当检测到性能不佳时自动切换到Two-Way算法以保证O(n)最坏时间
  • 搜索引擎： 使用倒排索引+高效匹配，不是简单的字符串匹配
  • 杀毒软件： 需要同时匹配成千上万个病毒特征码，使用Aho-Corasick多模式匹配算法
# Python中的字符串查找
text = "Hello World, Hello Python"

# find()：返回第一个匹配位置
print(text.find("Hello"))       # 0

# index()：和find类似，但找不到会抛异常
print(text.index("Hello"))      # 0

# count()：统计出现次数
print(text.count("Hello"))      # 2

# replace()：替换所有匹配
print(text.replace("Hello", "Hi"))  # "Hi World, Hi Python"

# 使用正则表达式进行复杂匹配
import re
results = re.findall(r"Hello \w+", text)
print(results)  # ['Hello World', 'Hello Python']

⚠️ 常见误区

  • 误区1：“KMP是最好的字符串匹配算法” —— KMP在理论上很优美（最坏O(n+m)），但在实际文本处理中，BM通常更快，因为它能跳过更多字符。
  • 误区2：“暴力匹配没有存在的价值” —— 当模式串很短（1-3个字符）时，暴力匹配简单高效，不需要预处理时间。很多编程语言的内置实现在短模式串时就是暴力匹配。
  • 误区3：“学KMP就是为了面试” —— KMP的核心思想——利用已知信息避免重复计算——是一种通用的算法思想，在很多其他问题中都有应用。

七、动手实战——构建一个简易全文搜索引擎

class SimpleSearchEngine:
    """简易全文搜索引擎"""

    def __init__(self):
        self.documents = {}  # id -> 文本
        self.index = {}      # 关键词 -> {文档id: [出现位置列表]}

    def add_document(self, doc_id, text):
        """添加文档并建立索引"""
        self.documents[doc_id] = text
        words = text.lower().split()
        for pos, word in enumerate(words):
            word = word.strip(".,!?;:")
            if word not in self.index:
                self.index[word] = {}
            if doc_id not in self.index[word]:
                self.index[word][doc_id] = []
            self.index[word][doc_id].append(pos)

    def search(self, query):
        """搜索包含关键词的文档"""
        query = query.lower().strip()
        if query not in self.index:
            return []
        results = []
        for doc_id, positions in self.index[query].items():
            results.append({
                'doc_id': doc_id,
                'occurrences': len(positions),
                'preview': self.documents[doc_id][:100]
            })
        # 按出现次数排序
        results.sort(key=lambda x: -x['occurrences'])
        return results

# 使用
engine = SimpleSearchEngine()
engine.add_document(1, "Python is a great programming language for data science")
engine.add_document(2, "Data structures and algorithms are fundamental in programming")
engine.add_document(3, "Python data analysis with pandas and numpy")

results = engine.search("data")
for r in results:
    print(f"文档{r['doc_id']}（出现{r['occurrences']}次）: {r['preview']}")

📝 掌握度自测

  1. 概念题： 用自己的话解释KMP算法的next数组是什么意思。为什么它能帮助跳过不必要的比较？
  2. 手算题： 计算模式串 “ABABACA” 的next数组。
  3. 分析题： BM算法为什么在实际中通常比KMP更快？在什么情况下BM会比KMP慢？
  4. 编码题： 用任意一种匹配算法，实现一个函数，统计模式串在文本中出现的总次数（允许重叠）。比如 “ABA” 在 “ABABABA” 中出现3次。
  5. 设计题： 如果你需要在一个大型代码仓库中搜索某个函数名，你会怎么设计搜索系统？需要考虑哪些因素？

💡 自我评估

  • 全部答对：字符串匹配算法已经是你的利器了。
  • 答对3-4题：理解透彻，KMP的next数组构建过程可以再多模拟几遍。
  • 答对1-2题：字符串匹配算法确实是一个难点。建议先彻底理解暴力匹配的过程，再对比理解KMP的改进之处。
  • 全部答错：这一章内容确实比较抽象。建议用具体的短字符串手动模拟每一步匹配过程。

到目前为止，我们已经学习了各种数据结构和具体的算法。但解决问题光有工具还不够，还需要”解题思路”——面对一个全新的问题，应该用什么策略去拆解它？下一章，我们将学习算法设计的三大核心思想：动态规划、贪心与回溯。它们不是具体的数据结构，而是解决问题的方法论。

购买课程解锁全部内容

刷题到通关：数据结构与算法面试实战

¥29.90