《数据结构与算法》（八）- 串详解

前言

部分内容摘自程杰的《大话数据结构》

1. 串的定义

  早先的计算机在被发明时，主要作用是做一些科学和工程的计算工作， 也就是现在我们理解的计算器，只不过它比小小计算器功能更强大、速度更快一些。 后来发现，在计算机上作非数值处理的工作越来越多，使得我们不得不需要引入对字符的处理。于是就有了字符串的概念。
  比如我们现在常用的搜索引擎，当我们在文本框中输入 “数据” 时，它已经把我们想要的 “数据分析” 列在下面了。显然这里网站作了一个字符串查找匹配的工作，如下图所示。

  今天我们就是来研究 “串” 这样的数据结构。先来看定义。

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。

  一般记为 s=“a$_1$a$_2$……a$_n$” (n>0)， 其中，s是串的名称，用双引号（也可以用单引号）括起来的字符序列是串的值，注意引号不属于串的内容。a$_i$ (1≤i≤n) 可以是字母、数字或其他字符，i就是该字符在串中的位置。串中的字符数目n称为串的长度，定义中谈到 “有限” 是指长度n是一个有限的数值。零个字符的串称为空串（null string），它的长度为零，可以直接用两双引号 ““”” 表示，也可以用希腊字母 “∅” 来表示。所谓的序列，说明串的相邻字符之间具有前驱和后继的关系。
  还有一些概念需要解释。
  空格串，是只包含空格的串。注意它与空串的区别，空格串是有内容有长度的，而且可以不止一个空格。
  子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。
  子串在主串中的位置就是子串的第一个字符在主串中的序号。
  开头提到的 “over”、“end”、“Iie” 其实可以认为是 “ bover”、“friend" 、“believe” 这些单词字符串的子串。

2. 串的比较

  两个数字，很容易比较大小。2 比 1 大，这完全正确，可是两个字符串如何比较？比如 “silly”、“stupid” 这样的同样表达 “愚蠢的” 的单词字符串，它们在计算机中的大小其实取决于它们挨个字母的前后顺序。它们的第一个字母都是 “s”，我们认为不存在大小差异，而第二个字母，由于 “i” 字母比 “t” 字母要靠前，所以 “i” < “t” ，于是我们说 “silly” < “stupid”。
  事实上，串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。
  计算机中的常用字符是使用标准的ASCII编码，更准确一点，由 7 位二进制数表示一个字符，总共可以表示 128 个字符。后来发现一些特殊符号的出现，128 个不够用，于是扩展ASCII码由 8 位二进制数表示一个字符， 总共可以表示 256 个字符，这已经足够满足以英语为主的语言和特殊符号进行输入、存储、输出等操作的字符需要了。可是，单我们国家就有除汉族外的满、回、藏、蒙古、维吾尔等多个少数民族文字，换作全世界估计要有成百上千种语言与文字，显然这 256 个字符是不够的，因此后来就有了Unicode编码，比较常用的是由 16 位的二进制数表示一个字符，这样总共就可以表示 216 个字符，约是 65 万多个字符，足够表示世界上所有语言的所有字符了。当然，为了和ASCII码兼容，Unicode的前 256 个字符与ASCII码完全相同。
  所以如果我们要在C语言中比较两个串是否相等，必须是它们串的长度以及它们各个对应位置的字符都相等时，才算是相等。即给定两个串：s=“a$_1$a$_2$……a$_n$”，t=“b$_1$b$_2$……b$_m$” ，当且仅当 n=m，且 a$_1$=b$_2$，a$_2$=b$_2$，……，a$_n$=b$_m$ 时，我们认为s=t。
  那么对于两个串不相等时，如何判定它们的大小呢。我们这样定义：
  给定两个串：s=“a$_1$a$_2$……a$_n$”，t=“b$_1$b$_2$……b$_m$” ，当满足以下条件之一时，s<t。

1. n<m，且 a$_1$=b$_1$（i=1，2，……，n）。
   例如当 s= “hap”，t “happy”，就有s<t。 因为t比s多出了两个字母。
2. 存在某个 k≤min (m, n)，使得 a$_i$=b$_i$ (i=1，2，……，k-1)，a$_k$<b$_k$。
   例如当 s=“happen”，t=“happy”，因为两串的前 4 个字母均相同，而两串第 5 个字母（k值），字母e的ASCII码是 101，而字母y的ASCII码是 121，显然e<y，所以s<t。

  再说一个字符申比较的应用。
  我们的英语词典，通常都是上万个单词的有序排列。就大小而言，前面的单词比后面的要小。你在查找单词的过程，其实就是在比较字符串大小的过程。

3. 串的抽象数据类型

  串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符，哪怕串中的字符是 “123” 这样的数字组成，或者 “2010-10-10” 这样的日期组成，它们都只能理解为长度为 3 和长度为 10 的字符串，每个元素都是字符而已。
  因此，对于串的基本操作与线性表是有很大差别的。线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素，但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作。

ADT 串(string)
Data
	串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
	StrAssign(T,*chars)：生成一个其值等于字符串常量chars的串T。
	StrCopy(T,S)：串S存在，由串S复制得串T。
	ClearString(S)：事S存在，将串清空。
	StringEmpty(S)：若串S为空，返回true,否则返回false。
	StrLength(S)：返回串S的元素个数，即串的长度。
	StrCompare(S,T)：若S>T,返回值>0，若S=T,返回0,若S<T,返回值<0。
	Concat(T,S1,S2)：用个返回由S1和S2联接而成的新串。
	Substring(Sub,S,pos,len)：串S存在，1≤pos≤StrLength(S)，
							且0≤len≤StrLength(S)-pos+1,用Sub返
							回事S的第pos个字符起长度为len的子串。
	Index(S,T,pos)：串S和T存在，T是非空串，1≤pos≤StrLength(S)。
					若主串S中存在和事T值相同的子串，则返回它在主串S中
					第pos个字符之后第一次出现的位置，否则返回0。
	Replace(S,T,V)：串S、T和V存在，T是非空串。用V替换主串S中出现的所有
					与T相等的不重叠的子串。
	StrInsert(S,pos,T)：串S和T存在，1≤pos≤StrLength(S)+1。
						在串S的第pos个字符之前插入串T。
	StrDelete(S,pos,len)：串S存在，1≤poss≤StrLength(S)-len+1。
						从串S中删除第pos个字符起长度为len的子串。
endADT

  对于不同的高级语言，其实对串的基本操作会有不同的定义方法，所以同学们在用某个语言操作字符串时，需要先查看它的参考手册关于字符串的基本操作有哪些。不过还好，不同语言除方法名称外，操作实质都是相类似的。比如C#中，字符串操作就还有ToLower转小写、ToUpper转大写、IndexOf从左查找子串位置（操作名有修改）、LastIndexOf从右查找子串位置、Trim去除两边空格等比较方便的操作，它们其实就是前面这些基本操作的扩展函数。
  我们来看一个操作Index的实现算法。

/* T为非空串。若主串S中第pos个字符之后存在与T相等的子串，*/
/* 则返回第一个这样的子串在S中的位置，否则返回0 */
int Index(String S, String T, int pos)
{
	int n,m,i;
	String sub;
	if (pos > 0)
	{
		n = StrLength(s);	/* 得到主串S的长度 */
		m = StrLength(T);	/* 得到子串T的长度 */
		i = pos;
		while (i <= n-m+1)
		{
			SubString(sub,S,i,m);	/* 取主串第i个位置 */
									/* 长度与T相等子串给sub */
			if (StrCompare(sub,T) != 0)	/* 如果两串不相等 */
				++i;
			else						/* 如果两串相等 */
				return i;				/* 则返回1值 */
		}
	}
	return 0;	/* 若无子串与T相等，返回0 */
}

  当中用到了StrLength、SubString、StrCompare等基本操作来实现。

4. 串的存储结构

  串的存储结构与线性表相同，分为两种。

4.1 串的顺序存储结构

  串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。
  既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的 0 下标位置，有的书中也会定义存储在数组的最后一个下标位置。但也有些编程语言不想这么干，觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符，比如 “\0" 来表示串值的终结，这个时候，你要想知道此时的串长度，就需要遍历计算一下才知道了， 其实这还是需要占用一个空间，何必呢。

  刚才讲的串的顺序存储方式其实是有问题的，因为字符串的操作，比如两串的连接Concat、新串的插入StrInsert，以及字符串的替换Replace，都有可能使得串序列的长度超过了数组的长度MaxSize。
  于是对于串的顺序存储，有一些变化， 串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做 “堆"。 这个堆可由C语言的动态分配函数malloc()和free()来管理。

4.2 串的链式存储结构

  对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用 “#” 或其他非串值字符补全，如下图所示。

  当然，这里一个结点存多少个字符才合适就变得很重要，这会直接影响着串处理的效率，需要根据实际情况做出选择。
  但串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

5. 朴素的模式匹配算法

  试试看。想找一个单词在一篇文章（相当于一个大字符串）中的定位问题。这种子串的定位操作通常称做串的模式匹配，应该算是串中最重要的操作之一。
  假设我们要从下面的主串 S=“goodgoogle” 中， 找到 T=“google” 这个子串的位置。我们通常需要下面的步骤。

1. 主串S第一位开始，S与T前三个字母都匹配成功，但S第四个字母是d而T的是g。第一位匹配失败。如下图所示，其中竖直连线表示相等，闪电状弯折连线表示不等。
   
2. 主串S第二位开始，主串S首字母是O，要匹配的T首字母是g，匹配失败，如下图所示。
   
3. 主串S第三位开始，主串S首字母是O，要匹配的T首字母是g，匹配失败，如下图所示。
   
4. 主串S第四位开始，主串S首字母是d，要匹配的T首字母是g，匹配失败，如下图所示。
   
5. 主串S第五位开始，S与T，6 个字母全匹配，匹配成功，如下图所示。
   

  简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。
  前面我们已经用串的其他操作实现了模式匹配的算法Index。 现在考虑不用串的其他操作，而是只用基本的数组来实现同样的算法。注意我们假设主串S和要匹配的子串T的长度存在S[0]与T[0]中。实现代码如下：

/* 返回子串T在串TS中第pos个字符之后的位置。若不存在，则函数返回值为0。 */
/* T非空，1≤pos≤StrLength(s)。*/
int Index(String s, String T, int pos)
{
	int i = pos;	/* i用于主串S中当前位置下标，若pos不为1*/
					/* 则从pos位置开始匹配 */
	int j = 1;	/* j用于子串T中当前位置下标值 */
	while(i <= S[0] && j <= T[0])/* 若i小于S长度且j小于T的长度时循环 */
	{
		if (S[i] == T[j])	/* 两字母相等则继续 */
		{
			++i;
			++j;
		}
		else	/* 指针后退重新开始匹配 */
		{
			i = i-j+2;	/* i退回到上次匹配首位的下一位 */
			j = 1;		/* j退回到子串T的首位 */
		}
	}
	if (j > T[0])
		return i-T[0];
	else
		return 0;
}

  分析一下， 最好的情况是什么？那就是一开始就区配成功， 比 “googlegood” 中去找 “google”，时间复杂度为O(1)。 稍差一些， 如果像刚才例子中第二、三、四位一样，每次都是首字母就不匹配，那么对T串的循环就不必进行了，比如 “abcdefgoogle” 中去找 “google”。那么时间复杂度为O(n+m)，其中n为主串长度，m为要匹配的子串长度。根据等概率原则，平均是(n+m)/2次查找，时间复杂度为O(n+m)。
  那么最坏的情况又是什么？就是每次不成功的匹配都发生在串T的最后一个字符。举一个很极端的例子。主串为 S= “0000000000000000000000000000000000000000000000000”，而要匹配的子串为 T=“0000000001”，前者是有 49 个 “0" 和 1 个 “1” 的主串，后者是 9 个 “0" 和 1 个 “1” 的子串。在匹配时，每次都得将T中字符循环到最后一位才发现：哦，原来它们是不匹配的。这样等于T串需要在S串的前 40 个位置都需要判断 10 次，并得出不匹配的结论，如下图所示。

  直到最后第 41 个位置，因为全部匹配相等，所以不需要再继续进行下去，如下图所示。如果最终没有可匹配的予串，比如是 T=“0000000002”，到了第 41 位置判断不匹配后同样不需要继续比对下去。因此最坏情况的时间复杂度为O((n-m+1)*m)。

  在实际运用中，对于计算机来说，处理的都是二进位的 0 和 1 的串，一个字符的ASCII码也可以看成是 8 位的二进位 01 串，当然，汉字等所有的字符也都可以看成是多个 0 和 1 串。再比如像计算机图形也可以理解为是由许许多多个 0 和 1 的串组成。所以在计算机的运算当中，模式匹配操作可说是随处可见，而刚才的这个算法，就显得太低效了。

6. KMP模式匹配算法

在很多年前我们的科学家们，觉得像这种有多个 0 和 1 重复字符的字符串，却需要挨个遍历的算法是非常糟糕的事情。于是有三位前辈，D.E.Knuth、J.H.Morris 和 V.R.Pratt（其中 Knuth 和 Pratt 共同研究，Morris 独立研究）发表一个模式匹配算法，可以大大避免重复遍历的情况，我们把它称之为克努特—莫里斯—普拉特算法，简称KMP算法。

6.1 KMP模式匹配算法原理

  为了能讲清楚KMP算法，我们不直接讲代码，那样很容易造成理解困难，还是从这个算法的研究角度来理解为什么它比朴素算法要好。
  如果主串 S=“abcdefgab”，其实还可以更长一些， 我们就省略掉只保留前 9 位，我们要匹配的 T=“abcdex”，那么如果用前面的朴素算法的话，前 5 个字母，两个串完全相等，直到第 6 个字母，“f” 与 “x” 不等，如下图的①所示。

  接下来，按照朴素模式匹配算法，应该是如上图的流程②③④⑤⑥。即主串S中当i=2、3、4、5、6时，首字符与子串T的首字符均不等。
  似乎这也是理所当然，原来的算法就是这样设计的。可仔细观察发现。对于要匹配的子串T来说，“abcdex” 首字母 “a” 与后面的串 “bcdex” 中任意一个字符都不相等。也就是说，既然 “a” 不与自已后面的子串中任何一字符相等， 那么对于上图的①来说，前五位字符分别相等，意味着子串T的首字符 “a” 不可能与S串的第 2 位到第 5 位的字符相等。在上图中，②③④⑤的判断都是多余。
  注意这里是理解KMP算法的关键。如果我们知道T串中首字符 “a” 与T中后面的字符均不相等（注意这是前提，如何判断后面再讲）。而T串的第二位的 “b” 与S串中第二位的 “b” 在上图的①中已经判断是相等的，那么也就意味着，T串中首字符 “a" 与S串中的第二位 “b” 是不需要判断也知道它们是不可能相等了，这样上图的②这一步判断是可以省略的，如下图所示。

  同样道理，在我们知道T串中首字符 “a” 与T中后面的字符均不相等的前提下，T串的 “a” 与S串后面的 “c”、“d”、“e” 也都可以在①之后就可以确定是不相等的，所以这个算法当中②③④⑤没有必要，只保留①⑥即可，如下图所示。

  之所以保留⑥中的判断是因为在①中T[6]≠S[6]，尽管我们已经知道T[1]≠T[6]，但也不能断定T[1]一定不等于S[6]，因此需要保留⑥这步。
  有人就会问，如果T串后面也含有首字符 “a” 的字符怎么办呢？
  我们来看下面一个例子，假设 S=“abcabcabc"，T=“abcabx” 。对于开始的判断，前 5 个字符完全相等，第 6 个字符不等，如下图的①。此时，根据刚才的经验，T的首字符 “a” 与T的第二位字符 “b”、第三位字符 “c” 均不等，所以不需要做判断，下图的朴素算法步骤②③都是多余。

  因为T的首位 “a” 与T第四位的 “a” 相等，第二位的 “b” 与第五位的 “b” 相等。而在①时，第四位的 “a” 与第五位的 “b” 已经与主串S中的相应位置比较过了，是相等的， 因此可以断定，T的首字符 “a”。第二位的字符 “b” 与S的第四位字符和第五位字符也不需要比较了，肯定也是相等的——之前比较过了，还判断什么，所以④⑤这两个比较得出字符相等的步骤也可以省略。
  也就是说，对于在子串中有与首字符相等的字符，也是可以省略一部分不必要的判断步骤。如下图所示，省略掉右图的T串前两位 “a” 与 “b” 同S串中的 4、5 位置字符匹配操作。

  对比这两个例子，我们会发现在①时，我们的i值，也就是主串当前位置的下标是 6，②③④⑤，i值是 2、3、4、5，到了⑥，i值才又回到了 6。即我们在朴素的模式匹配算法中，主串的i值是不断地回溯来完成的。而我们的分析发现，这种回溯其实是可以不需要的——正所谓好马不吃回头草，我们的KMP模式匹配算法就是为了让这没必要的回溯不发生。
  既然i值不回溯，也就是不可以变小，那么要考虑的变化就是j值了。通过观察也可发现，我们屡屡提到了T串的首字符与自身后面字符的比较，发现如果有相等字符，j值的变化就会不相同。也就是说，这个j值的变化与主串其实没什么关系，关键就取决于T串的结构中是否有重复的问题。
  比如下图中，由于 T=“abcdex”，当中没有任何重复的字符，所以j就由 6 变成了 1。而上图中，由于 T=“abcabx”，前缀的 “ab” 与最后 “x” 之前串的后缀 “ab” 是相等的。因此j就由 6 变成了 3。因此，我们可以得出规律，j值的多少取决于当前字符之前的串的前后缀的相似度。

  也就是说，我们在需要查找字符串前，先对要查找的字符串做一个分析，这样可以大大减少我们查找的难度，提高查找的速度。
  我们把T串各个位置的j值的变化定义为一个数组next，那么next的长度就是T串的长度。于是我们可以得到下面的函数定义：

6.2 next数组值的推导

  具体如何推导出一个串的next数组值呢，我们来看一些例子。

1. T=“abcdex” （如下表所示）
   
   ①当j=1时，next[1]=0；
   ②当j=2时，i由 1 到i-1就只有字符 “a"，属于其他情况next[2]=1；
   ③当j=3时，i由 1 到j-1串是 “ab”，显然 “a” 与 “b” 不相等，属其他情况，next[3]=1；
   ④以后同理，所以最终此T串的next[j]为 011111。
2. T=“abcabx” （如下表所示）
   
   ①当j=1时，next[1]=0；
   ②当j=2时，同上例说明，next[2]=1；
   ③当j=3时， 同上，next[3]=1；
   ④当j=4时，同上，next[4]=1；
   ⑤当j=5时，此时j由 1 到j-1的串是 “abca”，前缀字符 “a” 与后缀字符 “a” 相等（前缀用下划线表示，后缀用斜体表示），因此可推算出k值为 2（由 $´p{_1}···p{_k}{_-}{_1}´=´p{_j}{_-}{_k}{_+}{_1}···p{_j}{_-}{_1}´$，得到 $p_1=p_4$） 因此next[5]=2；
   ⑥当j=6时，j由 1 到j-1的串是 “abcab”，由于前缀字符 “ab” 与后缀 “ab” 相等，所以next[6]=3。

  我们可以根据经验得到如果前后缀一个字符相等，k值是 2，两个字符k值是 3，n个相等k值就是n+1。

3. T=“ababaaaba”（如下表所示）
   
   ①当j=1时，next[1]=0；
   ②当j=2时，同上next[2]=1；
   ③当j=3时，同上next[3]=1；
   ④当j=4时，j由 1 到j-1的串是 “aba”，前缀字符 “a” 与后缀字符 “a” 相等，next[4]=2；
   ⑤当j=5时，j由 1 到j-1的串是 “abab”，由于前缀字符 “ab” 与后缀 “ab” 相等，所以next[5]=3；
   ⑥当j=6时，j由 1 到j-1的串是 “ababa”，由于前缀字符 “aba” 与后缀 “aba” 相等，所以next[6]=4；
   ⑦当j=7时，j由 1 到j-1的串是 “ababa”，由于前缀字符 “ab” 与后缀 “aa” 并不相等，只有 “a” 相等，所以next[7]=2；
   ⑧当j=8时，j由 1 到j-1的串是 “ababaa”，只有 “a" 相等，所以next[8]=2；
   ⑨当j=9时，i由 1 到j-1的串是 “ababaab”，由于前缀字符 “ab” 与后缀 “ab” 相等，所以next[9]=3。
4. T=“aaaaaab”（如下表所示）
   
   ①当j=1时，next[1]=0；
   ②当j=2时，同上next[2]=1；
   ③当j=3时，j由 1 到j-1的串是 “a”，前缀字符 “a” 与后缀字符 “a” 相等，next[3]=2；
   ④当j=4时, j由 1 到j-1的串是 “aa”，由于前缀字符 “aa” 与后缀 “aa” 相等，所以next[4]=3；
   ⑤ ······
   ⑥当j=9时，j由 1 到j-1的串是 “aaaaaaaa”，由于前缀字符 “aaaaaaa” 与后缀 “aaaaaaa” 相等，所以next[9]=8。

6.3 KMP模式匹配算法实现

/* 通过计算返回子串T的next数组。*/
void get_ next(String T, int *next)
{
	int i,k;
	i=1;
	k=0;
	next[1]=0;
	while (i<T[0])	/* 此处T[0]表示串T的长度 */
	{
		if(k==0 || T[i]==T[k])
		{
			++i;
			++k;
			next[i] = k;
		}
		else
			k = next[k];	/* 若字符不相同，则k值回溯 */
	}
}

  上面这段代码的目的就是为了计算出当前要匹配的串T的next数组。

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。*/
/* T非空，1≤pos≤StrLength(S)。*/
int Index_KMP(String s, String T, int pos)
{
	int i = pos;	/* i用于主串S当前位置下标值，从pos位置开始匹配 */
	int j = 1;	/* j用于子串T中当前位置下标值 */
	int next[255];	/* ★★★定义一next数组 */	
	get_ next(T, next);	/* ★★★对串T作分析，得到next数组 */
	while (i <= S[0] && j <= T[0])	/* 当i小于S的长度且j小于T的长度时，循环继续 */
	{
		if (j==0 || S[i] == T[j])	/* 两字母相等则继续，与朴素算法增加了j=0的判断 */
		{
			++i;
			++j;
		}
		else	/* 指针后退重新开始匹配 */
		{
			j= next[j];	/* ★★★j退回合适的位置，i值不变 */
		}
	}
	if (j > T[0])
		return i-T[0];
	else
		return 0:
}

  上面这段代码的while循环是真正在匹配查找。
  加★★★的为相对于朴素匹配算法增加的代码，改动不算大，关键就是去掉了i值回溯的部分。对于get_next函数来说，若T的长度为m，因只涉及到简单的单循环，其时间复杂度为O(m)，而由于i值的不回溯，使得index_KMP算法效率得到了提高，while循环的时间复杂度为O(n)。 因此，整个算法的时间复杂度为O(n+m)。相较于朴素模式匹配算法的 O((n-m+1)*m) 来说，是要好一些。
  这里也需要强调，KMP算法仅当模式与主串之间存在许多 “部分匹配” 的情况下才体现出它的优势，否则两者差异并不明显。

6.4 KMP模式匹配算法的改进

  后来有人发现，KMP还是有缺陷的。比如，如果我们的主串 S=“aaaabcde”，子串 T=“aaaaax”，其next数组值分别为 012345，在开始时，当i=5、 j=5时，我们发现 “b” 与 “a” 不相等，如下图的①，因此j=next[5]=4，如下图中的②，此时 “b” 与第 4 位置的 “a” 依然不等，j=next[4]=3，如下图中的③，后依次是④⑤，直到j=next[1]=0时，根据算法，此时i++、j++，得到i=6、j=1，如下图中的⑥。

  我们发现，当中的②③④⑤步骤，其实是多余的判断。由于T串的第二、三、四、五位置的字符都与首位的 “a” 相等，那么可以用首位next[1]的值去取代与它相等的字符后续next[j]的值，这是个很好的办法。因此我们对求next()函数进行了改良。
  假设取代的数组为nextval，增加了★★★部分，代码如下：

/* 求模式串T的next函数修正值并存入数组nextval */
void get_ next(String T, int *next)
{
	int i,k;
	i=1;
	k=0;
	next[1]=0;
	while (i<T[0])	/* 此处T[0]表示串T的长度 */
	{
		if(k==0 || T[i]==T[k])	/* T[i]表示后缀的单个字符，T[k]表示前缀的单个字符 */
		{
			++i;
			++k;
			if (T[i]!=T[k])	/* ★★★若当前字符与前缀字符不同 */
				next[i] = k;	/* ★★★则当前的k为nextval在i位置的值 */
			else
				nextval[i] = nextval[k];	/* 如果与前缀字符相同，则将前缀字符的 */
											/* nextval值赋值给nextval在i位置的值 */
		}
		else
			k = next[k];	/* 若字符不相同，则k值回溯 */
	}
}

  实际匹配算法，只需要将get_next (T,next);改为get_nextval (T,next);即可，这里不再重复。

6.5 nextval数组值推导

  改良后，我们之前的例子nextval值就与next值不完全相同了。比如：

1. T=“ababaaaba” (如下表所示)
   
   先算出next数组的值分别为 011234223，然后再分别判断。
   ①当j=1时，nextval[1]=0；
   ②当j=2时，因第二位字符" b" 的next值是 1，而第一位就是 “a”，它们不相等，所以nextval[(2]=next[2]=1，维持原值。
   ③当j=3时，因为第三位字符 “a” 的next值为 1，所以与第一位的“a" 比较得知它们相等，所以nextval[3]=nextval[1]=0；如下图所示。
   
   ④当j=4时，第四位的字符 “b” next值为 2，所以与第二位的 “b” 相比较得到结果相等，因此nextval[4]=nextval[2]=1；如下图所示。
   
   ⑤当j=5时，next值为3，第五个字符 "a” 与第三个字符 “a” 相等，因此nextval[5]=nextval[3]=0；
   ⑥当j=6时，next值为 4，第六个字符 “a” 与第四个字符 “b” 不相等，因此nextval[6]=4；
   ⑦当j=7时，next值为 2，第七个字符 “a” 与第二个字符 “b” 不相等，因此nextval[7]=2；
   ⑧当j=8时，next值为 2，第八个字符 “b” 与第二个字符 “b” 相等，因此nextval[8]=nextval[2]=1；
   ⑨当j=9时，next值为 3，第九个字符 “a” 与第三个字符 “a” 相等，因此nextval[9]=nextval[3]=0。
2. T=“aaaaaaaab”（如下表）
   
   先算出next数组的值分别为 012345678，然后再分别判断。
   ①当j=1时，nextval[1]=0；
   ②当j=2时，next值为 1，第二个字符与第一个字符相等，所以nextval[2]=nextval[1]=0；
   ③同样的道理，其后都为 0 ······
   ④当j=9时，next值为 8，第九个字符 “b” 与第八个字符 “a”不相等，所以nextval[9]=8。

  总结改进过的KMP算法，它是在计算出next值的同时，如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自已a位的next的值。

7. 总结

  串（string）是由零个或多个字符组成的有限序列，又名叫字符串。本质上,它是一种线性表的扩展，但相对于线性表关注一个个元素来说，我们对串这种结构更多的是关注它子串的应用问题，如查找、替换等操作。现在的高级语言都有针对串的函数可以调用。我们在使用这些函数的时候，同时也应该要理解它当中的原理，以便于在碰到复杂的问题时，可以更加灵活的使用，比如KMP模式匹配算法的学习，就是更有效地去理解index函数当中的实现细节。