4.2　字符串处理

字符串（String）是由零个或多个字符组成的有限序列。一般记为s=“a₀a₁…a_n-1”，其中s是字符串名，用双引号作为分界符括起来的a₀a₁…a_n-1称为串值，其中的a_i（0≤i≤n-1）是字符串中的字符。字符串中字符的个数称为字符串的长度。字符串的串结束符'\0'不作为字符串中的字符，也不被计入字符串的长度。双引号间也可以没有任何字符，这样的字符串称为空串。显然，字符串是一种以字符为元素的线性表，具有线性表的有限性、有序性和均匀性；线性表可以为空，字符串也可以是空串。由于可以按下标直接存取字符串中的某一字符，因此字符串一般属于直接存取类的线性表。当然，字符串也可以采用链式存储结构，不过这样的情形并不多见。本节实验中的字符串主要以直接存取类线性表为存储结构。

本节给出字符串三个方面的实验：

·使用字符串作为存储结构；

·判断一个字符串是否为另一个字符串的子串；如果是，那么求出子串在主串的匹配位置，即模式匹配问题；

·求最长回文子串的Manacher算法。