字符串匹配介绍

字符串匹配算法也称为“字符串搜索算法”。这是一个重要的字符串算法类别，定义为“这是一种查找在一个更大的字符串中找到一个或多个字符串的位置的方法。”

给定一个文本数组 T [1.....n]，包含 n 个字符，以及一个模式数组 P [1......m]，包含 m 个字符。 问题是找到一个整数 s，称为**有效位移**，其中 0 ≤ s < n-m 并且 T [s+1......s+m] = P [1......m]。 换句话说，要找到 P 是否在 T 中，即 P 是否是 T 的子串。 P 和 T 的元素是从某个有限字母表中提取的，例如 {0, 1} 或 {A, B .....Z, a, b..... z}。

给定一个字符串 T [1......n]，**子字符串**表示为 T [i......j]，对于某些 0≤i ≤ j≤n-1，该字符串由 T 中从索引 i 到索引 j（包括 i 和 j）的字符形成。 此过程表明字符串是自身的子字符串（取 i = 0 和 j = m）。

字符串 T [1......n] 的**真子字符串**是 T [1......j]，对于某些 0<i ≤ j≤n-1。 也就是说，我们必须有 i>0 或 j < m-1。

使用这些描述，我们可以说给定任何字符串 T [1......n]，子字符串是

而真子字符串是

注意：如果 i>j，则 T [i.....j] 等于空字符串或 null，其长度为零。

用于字符串匹配的算法

有不同的方法用于查找字符串

1. 朴素字符串匹配算法
2. Rabin-Karp 算法
3. 有限自动机
4. Knuth-Morris-Pratt 算法
5. Boyer-Moore 算法