串

串是仅由字符构成的有限序列，是一种特殊的线性表，其数据元素为字符，因此通常称呼为字符串。一般标记为S='a1a2a3...an'。

• 基本概念

空串：长度为零，不包含任何字符的串。

空格串：由一个或多个空格组成的串（空格也是字符）；

子串：串中任意连续字符构成的序列称为子串，含有子串的串称为主串。子串在主串中的位置是指该子串首次出现时，子串第一个字符在主串中的位置。

串相等：两个串的长度相等，并且对于序列的的字符也相同。

串比较：以字符的ASCII码值做为依据。从两个串的第一个字符开始，字符的码大者，所在的串为大。若其中一个串先结束，则以串长者为大。

如下图JAVA JDK中字符串比较方法所示：

字符串value与字符串anotherString比较，若执行结果为正数，则value大于anotherString，结果为负数，则anotherString大于value。为零，则两个字符串相等。

• 存储结构

顺序存储：

用一组地址连续的存储单元来存储串值得字符序列。可以根据串的字符数定义存储空间，也可以根据串长的需要，动态申请空间。

链式存储：

链的每个结点可以存储一个字符，也可以存储多个字符。因链结点的大小会影响处理效率，所以要考虑存储密度。

• 匹配模式

子串的定位操作，称为串的匹配模式。子串也称为模式串。

朴素的模式匹配算法：

该算法也被称为布鲁特-福斯算法。

该算法的思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐一对模式串进行后续比较，否则，从主串的第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和主串中的一个连续字符序列相等时为止。如果在主串中找不到与模式串相同的，则匹配失败。

若主串和模式串的长度分别是n和m,则最好情况，时间复杂度为O(n+m)，最坏情况，时间复杂度为O(n*m)。

改进的模式匹配算法（KMP）：

改进之处在于，当匹配过程中出现相比较的字符不相等时，不需要回退主串的字符位置指针，而是利用已经得到的“部分匹配”的字符，将模式串向右滑动尽可能远的距离，再进行比较。具体向右滑动多少距离，就得依据next函数值进行计算。依据模式串next函数值整理的表，就叫《部分匹配表》。

滑动距离=已“部分匹配”的字符数-next函数值。

next函数定义如下：

JAVA脚本如下：

private int[] next(String pattern) {
 char[] p = pattern.toCharArray(); //模式串字符组
 int[] next = new int[p.length];
 next[0] = -1; //定义下标0为字符串的开始，规定next[0]=-1;
 int i = 0;
 int j = -1;
 while(i < p.length - 1) {
 if (j == -1 || p[i] == p[j]) {
 i++;
 j++;
 next[i] = j;
 } else {
 j = next[j];
 }
 }
 return next;
}