字符串匹配

字符串匹配问题
术语名称	字符串匹配问题
英语名称	string-matching problem
别名	字符串搜索问题, string-searching problem

字符串匹配问题是一种常见的实际问题，目标是在长字符串中寻找其是否包含某短字符串，以及给出其第一次出现位置。 字符串匹配在文本搜索功能、DNA序列搜索、自然语言处理等诸多场景中均有广泛应用。

在这类问题中，通常称长字符串为“文本(text)”，短字符串为“模式(pattern)”。有时也视为模式匹配问题的一种。

问题模型

给定文本串 [math]\displaystyle{ s }[/math] ，模式串 [math]\displaystyle{ p }[/math] ，记 [math]\displaystyle{ n=|s|,m=|p| }[/math] ，判定是否存在索引 [math]\displaystyle{ i }[/math] 满足 [math]\displaystyle{ s_{i..i+p} = p }[/math] 。

主要算法

• 暴力算法（BF 算法，朴素算法）：对每个 [math]\displaystyle{ i }[/math] 尝试匹配。
• 基于自动机的算法
• 基于残余部分的算法： KMP 算法、 BM 算法
• 预处理文本

其他变体： AC 自动机： KMP 算法的变体，扩展至多模式的场景。