String Pattern Matching

Idea

String pattern matching finds occurrences of a pattern in a text. Classic algorithms: naive (BF), KMP, etc.

字符串模式匹配演示

此处可扩展为KMP等算法的匹配过程动画。

• 主串与模式串对齐
• next数组跳转演示
• 匹配/失配过程

Algorithms

Naive (Brute Force)

• Align pattern and text, compare sequentially
• Time $O(mn)$, $m$ text length, $n$ pattern length

KMP

• Uses prefix table (next array) to avoid re-checking
• Time $O(m+n)$

Scenarios

• Text editor find/replace
• DNA sequence analysis
• Search/retrieval, data mining

Pseudo-code

Naive:

for i = 0 to m-n:
    for j = 0 to n-1:
        if S[i+j] != P[j]:
            break
    if j == n:
        return i // match
return -1

KMP (simplified):

build next array
i = 0, j = 0
while i < m:
    if S[i] == P[j]:
        i++, j++
        if j == n: return i-n // match
    else if j > 0:
        j = next[j-1]
    else:
        i++
return -1

Complexity

• Naive: $O(mn)$
• KMP: $O(m+n)$

Exercises

Exercise 1

Explain KMP idea and its advantage.

参考答案

思路：next 避免重复比较。

步骤：

1. 用 next 跳过已匹配前缀
2. 时间 $O(m+n)$

答案：next 让主串不回溯，提效。

Exercise 2

Time complexity of naive vs KMP?

参考答案

思路：直接比较。

步骤：

1. 朴素 $O(mn)$
2. KMP $O(m+n)$

答案：朴素 $O(mn)$，KMP $O(m+n)$。

Past exam

2022·408

KMP 如何避免主串指针回溯？

参考答案

思路：next 数组跳转。

步骤：

1. 匹配失败主串不回溯
2. 模式串按 next 跳

答案：用 next 跳转模式串，主串不回溯。

PreviousB-Tree and B+Tree SearchStructures of B-/B+ trees, search process, complexity, and practice. NextSearching Algorithms: Analysis & ApplicationsCompare searching algorithms, complexity, space, scenarios, and mixed exercises.