字符串匹配

字符串的具体实现并不难，借助之前的线性表数据结构即可轻松实现，在本节我们重点讨论字符串的相关算法。

概念

字符串简称为串，是指由 字母表 \(\sum\) 的字符所组成的 有限序列，即 \(S=a_0a_1a_2...a_{n-1} \in \sum^*\)。

字符串与常规的线性表又有些许不同，通常，字符的种类不多，而\(串长=n \gg |\sum|\)。

一般地，如果一个名为 S 的字符串由 n 个字符构成，我们就将所有的字符从前至后编号为 0 至 n-1，并按照我们的惯例，记作 S[0, n)，而串中秩为 k 的字符，也相应地记作 S[k]。

两个字符串相等是指 S[0, n) = T[0, m)，即长度相等（n = m），且对应的字符均相同（S[i] = T[i]）。

对于任何一个字符串 S 而言，由 i 和 k 所指定的那个子串，也就是从秩为 i 的那个字符开始，连续的 k 个字符。

所谓的前缀（prefix）是子串的一个特例，具体来说，所谓长度为 k 的前缀，也就是起始于首字符的前 k 个字符。

对称的，所谓长度为 k 的后缀（suffix），也就是终止于末元素的最靠后的 k 个字符。

不难验证，所谓起始于 i，长度为 k 的子串，也就是在长度为 i+k 的前缀中，长度为 k 的后缀。

对于串长 n 为 0 的串称之为空串，空串与由空格组成的串并不是一回事，空串是任何串的子串、前缀、后缀。

此外，任何串也是其自身的子串、前缀、后缀。反过来，长度严格小于原串的子串、前缀、后缀也称作真子串、真前缀、真后缀。

注意，从上面可以看出子串和子序列不是一回事，子串是连续的，子序列则未必连续。

字符串匹配具体指在文本串 T 中找到模式串 P 的过程。记 \(n=|T|\) 和 \(m=|P|\)，通常有 \(n\gg m\gg 2\)。

字符串匹配又称模式匹配（pattern matching），其可以分为 4 个层次：

我们本节重点讨论第 2 个层次。