字符串匹配
更新: 10/24/2025 字数: 0 字 时长: 0 分钟
1.概述
字符串是由若干个字符组成的有限序列，它有很多经典的算法，本文将介绍其中的串匹配算法。
字符串的匹配问题是指查找一个模式串Pattern在文本串Text中的位置，如下面代码所示：
java
String text = "ababcabcacbab"; // length = 13
String pattern = "abcac";
int index = text.indexOf(pattern); // index = 5
pattern = "ab";
index = text.lastIndexOf(pattern); // index = 11上面代码中，indexOf和lastIndexOf方法分别返回模式串P在主串S中第一次和最后一次出现的位置，它们底层实现了字符串匹配算法，下面介绍几种经典的字符串匹配算法：
- 蛮力匹配（Brute Force）
- KMP（Knuth-Morris-Pratt）
- BM（Boyer-Moore）
- Rabin-Karp
- Sunday
在讲解之前，先了解几个概念（假设字符串为thank）：前缀（prefix）、真前缀（proper prefix）、后缀（suffix）、真后缀（proper suffix）。
注意：在后文中使用tlen表示文本串Text的长度，plen表示模式串Pattern的长度。