编辑“︁字符串匹配算法”︁（章节）

= 字符串匹配算法 =

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

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

<math>
\begin{cases}
T = t_1 t_2 \cdots t_n \\
P = p_1 p_2 \cdots p_m \\
\text{找到所有 } s \text{ 使得 } t_{s+i-1} = p_i \text{ 对 } 1 \leq i \leq m
\end{cases}
</math>

== 朴素算法（Brute-Force）==
最简单的字符串匹配方法，逐个比较文本和模式的字符。

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

=== 代码示例 ===
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

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

== Knuth-Morris-Pratt (KMP) 算法 ==
通过预处理模式字符串构建'''部分匹配表'''（Partial Match Table），利用已匹配信息跳过不必要的比较。

=== 部分匹配表 ===
对于模式 ''P''，定义部分匹配表 ''π''：
<math>
\pi[i] = \max\{k \mid k < i \text{ 且 } P[0..k-1] \text{ 是 } P[0..i-1] \text{ 的后缀}\}
</math>

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

=== 代码示例 ===
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

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

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

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

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

=== 代码示例 ===
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

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

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

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

=== 代码示例 ===
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

=== 复杂度分析 ===
* 平均情况：O(n + m)
* 最坏情况：O(n×m)（当所有子串哈希冲突时）

== 算法比较 ==
{| class="wikitable"
|+ 字符串匹配算法比较
! 算法 !! 预处理时间 !! 匹配时间 !! 空间复杂度 !! 特点
|-
| 朴素算法 || 无 || 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. '''搜索引擎'''：构建倒排索引时处理关键词

== 可视化示例 ==
<mermaid>
graph TD
    A[开始匹配] --> B{字符匹配?}
    B -->|是| C[移动到下个字符]
    B -->|否| D[根据规则跳跃]
    C --> E{完全匹配?}
    E -->|是| F[记录位置]
    E -->|否| B
    D --> B
</mermaid>

== 总结 ==
字符串匹配算法是计算机科学中的基础问题，不同算法在不同场景下各有优势：
* 对于短模式和小字母表，Boyer-Moore通常表现最佳
* 对于理论保证，KMP提供线性最坏情况复杂度
* 对于多模式匹配，Rabin-Karp可以扩展

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

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:算法基础]]