字符串匹配算法[编辑 | 编辑源代码]

字符串匹配算法是计算机科学中用于在较大文本中查找特定模式（子字符串）出现位置的一类算法。这类算法在文本编辑器、搜索引擎、生物信息学等领域有广泛应用。

基本概念[编辑 | 编辑源代码]

字符串匹配问题可以形式化定义为：给定一个文本字符串 T（长度为 n）和一个模式字符串 P（长度为 m），找出所有满足 T[s..s+m-1] = P 的起始位置 s。

${\begin{cases} T = t_{1} t_{2} \dots t_{n} \\ P = p_{1} p_{2} \dots p_{m} \\ 找到所有 s 使得 t_{s + i - 1} = p_{i} 对 1 \leq i \leq m \end{cases}$

朴素算法（Brute-Force）[编辑 | 编辑源代码]

最简单的字符串匹配方法，逐个比较文本和模式的字符。

算法步骤[编辑 | 编辑源代码]

1. 从文本的第一个字符开始 2. 将模式与文本当前位置对齐 3. 逐个比较对应字符 4. 如果完全匹配则记录位置 5. 移动一位，重复上述过程

代码示例[编辑 | 编辑源代码]

def brute_force_search(text, pattern):
    n = len(text)
    m = len(pattern)
    positions = []
    
    for s in range(n - m + 1):
        match = True
        for i in range(m):
            if text[s + i] != pattern[i]:
                match = False
                break
        if match:
            positions.append(s)
    
    return positions

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABC"
print(brute_force_search(text, pattern))  # 输出: [10]

复杂度分析[编辑 | 编辑源代码]

最坏时间复杂度：O(n×m)（当每次都在模式最后一个字符失配时）
最好时间复杂度：O(n)（当模式不在文本中时）

Knuth-Morris-Pratt (KMP) 算法[编辑 | 编辑源代码]

通过预处理模式字符串构建部分匹配表（Partial Match Table），利用已匹配信息跳过不必要的比较。

部分匹配表[编辑 | 编辑源代码]

对于模式 P，定义部分匹配表 π： $π [i] = \max {k ∣ k < i 且 P [0 . . k - 1] 是 P [0 . . i - 1] 的后缀}$

算法步骤[编辑 | 编辑源代码]

1. 预处理构建部分匹配表 2. 在匹配过程中，当出现不匹配时，根据部分匹配表移动模式

代码示例[编辑 | 编辑源代码]

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    lps = compute_lps(pattern)
    i = j = 0
    positions = []
    
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                positions.append(i - j)
                j = lps[j - 1]
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return positions

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABC"
print(kmp_search(text, pattern))  # 输出: [10]

复杂度分析[编辑 | 编辑源代码]

预处理时间：O(m)
匹配时间：O(n)
总时间复杂度：O(n + m)

Boyer-Moore 算法[编辑 | 编辑源代码]

利用两个启发式规则（坏字符规则和好后缀规则）从右向左比较模式，实现更快的跳跃。

坏字符规则[编辑 | 编辑源代码]

当发现不匹配字符时，将模式向右移动，使该字符与模式中最右出现的该字符对齐。

好后缀规则[编辑 | 编辑源代码]

当发现部分匹配的后缀时，将模式向右移动，使该后缀与模式中另一个相同子串对齐。

代码示例[编辑 | 编辑源代码]

def boyer_moore_search(text, pattern):
    def bad_char_heuristic(pattern):
        bad_char = [-1] * 256
        for i, c in enumerate(pattern):
            bad_char[ord(c)] = i
        return bad_char
    
    n = len(text)
    m = len(pattern)
    bad_char = bad_char_heuristic(pattern)
    positions = []
    s = 0
    
    while s <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1
        if j < 0:
            positions.append(s)
            s += (m - bad_char[ord(text[s + m])] if s + m < n else 1)
        else:
            s += max(1, j - bad_char[ord(text[s + j])])
    
    return positions

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABC"
print(boyer_moore_search(text, pattern))  # 输出: [10]

复杂度分析[编辑 | 编辑源代码]

最好情况：O(n/m)（当模式不在文本中时）
最坏情况：O(n×m)（当文本和模式都是重复字符时）

Rabin-Karp 算法[编辑 | 编辑源代码]

使用哈希技术，通过比较模式哈希值与文本子串哈希值来快速筛选可能匹配的位置。

算法原理[编辑 | 编辑源代码]

1. 计算模式的哈希值 2. 计算文本中所有长度为m的子串的哈希值 3. 比较哈希值，只有哈希值匹配时才进行实际字符比较

代码示例[编辑 | 编辑源代码]

def rabin_karp_search(text, pattern, d=256, q=101):
    n = len(text)
    m = len(pattern)
    h = pow(d, m - 1) % q
    p = t = 0
    positions = []
    
    # 预处理：计算模式和第一个窗口的哈希值
    for i in range(m):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q
    
    for s in range(n - m + 1):
        if p == t:
            match = True
            for i in range(m):
                if text[s + i] != pattern[i]:
                    match = False
                    break
            if match:
                positions.append(s)
        
        if s < n - m:
            t = (d * (t - ord(text[s]) * h) + ord(text[s + m]) % q
            t = t if t >= 0 else t + q
    
    return positions

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABC"
print(rabin_karp_search(text, pattern))  # 输出: [10]

复杂度分析[编辑 | 编辑源代码]

平均情况：O(n + m)
最坏情况：O(n×m)（当所有子串哈希冲突时）

算法比较[编辑 | 编辑源代码]

字符串匹配算法比较
算法	预处理时间	匹配时间	空间复杂度	特点
朴素算法	无	O(n×m)	O(1)	实现简单，效率低
KMP	O(m)	O(n)	O(m)	最坏情况下线性时间
Boyer-Moore	O(m + σ)	最好O(n/m)，最坏O(n×m)	O(m + σ)	实践中最快
Rabin-Karp	O(m)	平均O(n + m)，最坏O(n×m)	O(1)	适合多模式匹配

实际应用案例[编辑 | 编辑源代码]

1. 文本编辑器：查找/替换功能通常使用Boyer-Moore或其变种 2. 防病毒软件：扫描文件内容时使用高效的字符串匹配算法 3. DNA序列分析：在基因组中寻找特定序列模式 4. 搜索引擎：构建倒排索引时处理关键词

可视化示例[编辑 | 编辑源代码]

总结[编辑 | 编辑源代码]

字符串匹配算法是计算机科学中的基础问题，不同算法在不同场景下各有优势：

对于短模式和小字母表，Boyer-Moore通常表现最佳
对于理论保证，KMP提供线性最坏情况复杂度
对于多模式匹配，Rabin-Karp可以扩展

理解这些算法的原理和实现有助于在实际问题中选择合适的解决方案。