字符串匹配介绍

字符串匹配算法也称为“字符串搜索算法”。这是一类至关重要的字符串算法, 其声明为“这是一种在较大的字符串中找到多个字符串的地方的方法”。

给定n个字符的文本数组T [1 ….. n]和m个字符的模式数组P [1 … m]。问题在于找到一个整数s, 称为有效移位, 其中0≤s <n-m且T [s + 1 … s + m] = P [1 … m]。换句话说, 即使在T中找到P, 也就是P都是T的子串。P和T的项是从诸如{0, 1}或{A, B … ..Z, a, b ….. z}。

给定字符串T [1 …… n], 对于0≤i≤j≤n-1的子字符串表示为T [i …… j], 该字符串由从索引i到索引j（含）的T。字符串是其自身的子字符串的过程（取i = 0和j = m）。

对于某些0 <i≤j≤n-1, 字符串T [1 … n]的正确子字符串是T [1 … j]。也就是说, 我们必须让i> 0或j <m-1。

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

T [i.....j] = T [i] T [i +1] T [i+2]......T [j] for some 0≤i ≤ j≤n-1.

正确的子字符串是

T [i.....j] = T [i] T [i +1] T [i+2]......T [j] for some 0≤i ≤ j≤n-1.

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

用于字符串匹配的算法

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

1. 天真的字符串匹配算法
2. 拉宾·卡普算法
3. 有限自动机
4. Knuth-Morris-Pratt算法
5. Boyer-Moore算法