Chapter 5 串

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

串的定义

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。
一般记为s=”a1a2……an”(n≥0)，其中，s是串的名称，用双引号（有些书中也用单引号）括起来的字符序列是串的值，注意引号不属于串的内容。
ai（1≤i≤n）可以是字母、数字或其他字符，i就是该字符在串中的位置。
串中的字符数目n称为串的长度，定义中谈到“有限”是指长度n是一个有限的数值。
零个字符的串称为空串（nullstring），它的长度为零，可以直接用两双引号“”””表示，也可以用希腊字母“Φ”来表示。
所谓的序列，说明串的相邻字符之间具有前驱和后继的关系。

还有一些概念需要解释。

空格串，是只包含空格的串。注意它与空串的区别，空格串是有内容有长度的，而且可以不止一个空格。

子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。
子串在主串中的位置就是子串的第一个字符在主串中的序号。

串的比较

串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。

如果我们要在C语言中比较两个串是否相等，必须是它们串的长度以及它们各个对应位置的字符都相等时，才算是相等。即给定两个串：s=”a1a2……an”，t=”b1b2……bm”，当且仅当n=m，且a1=b1，a2=b2，……，an=bm时，我们认为s=t。

串的抽象数据类型

串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符。

因此，对于串的基本操作与线性表是有很大差别的。线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素，但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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):                      用T返回由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≤pos≤StrLength(S)-len+1。从串S中删除第pos个字符起长度为len的子串。
endADT

串的存储结构

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

串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做“堆”。这个堆可由C语言的动态分配函数malloc()和free()来管理。

串的链式存储结构

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

但串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

朴素的模式匹配算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*  返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。  */
/*  T非空，1≤pos≤StrLength(S)。  */
int  Index(String  S,  String  T,  int  pos)
{
	/*  i用于主串S中当前位置下标，若pos不为1  */
	/*  则从pos位置开始匹配  */
	int  i  =  pos;                             
	/*  j用于子串T中当前位置下标值  */
	int  j  =  1;                               
	/*  若i小于S长度且j小于T的长度时循环  */
	while  (i  <=  S[0]  &&  j  <=  T[0])       
	{
		/*  两字母相等则继续  */
		if  (S[i]  ==  T[j])                        
		{
			/*  指针后退重新开始匹配  */
			++i;++j;
		}
		else                                        
		{
			/*  i退回到上次匹配首位的下一位  */
			i  =  i  -  j  +  2;                        
			/*  j退回到子串T的首位  */
			j  =  1;                                    
		}
	}

	if  (j  =  T[0])
	{
		return  i  -  T[0];
	}
	else
	{
		return  0;
	}
}

KMP模式匹配算法


如果主串S=”abcdefgab”，与我们要匹配的T=”abcdex”，那么如果用前面的朴素算法的话，前5个字母，两个串完全相等，直到第6个字母，“f”与“x”不等，如图1的①所示。
接下来，按照朴素模式匹配算法，应该是如图1的流程②③④⑤⑥。即主串S中当i=2、3、4、5、6时，首字符与子串T的首字符均不等。

似乎这也是理所当然，原来的算法就是这样设计的。可仔细观察发现。对于要匹配的子串T来说，“abcdex”首字母“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于图1的①来说，前五位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2位到第5位的字符相等。在图1中，②③④⑤的判断都是多余。


注意这里是理解KMP算法的关键。如果我们知道T串中首字符“a”与T中后面的字符均不相等（注意这是前提，如何判断后面再讲）。
而T串的第二位的“b”与S串中第二位的“b”在图1的①中已经判断是相等的，那么也就意味着，T串中首字符“a”与S串中的第二位“b”是不需要判断也知道它们是不可能相等了，这样图1的②这一步判断是可以省略的，如图2所示。


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

之所以保留⑥中的判断是因为在①中T[6]≠S[6]，尽管我们已经知道T[1]≠T[6]，但也不能断定T[1]一定不等于S[6]，因此需要保留⑥这一步。

有人就会问，如果T串后面也含有首字符“a”的字符怎么办呢？


我们来看下面一个例子，假设S=”abcababca”，T=”abcabx”。对于开始的判断，前5个字符完全相等，第6个字符不等，如图5-7-4的①。此时，根据刚才的经验，T的首字符“a”与T的第二位字符“b”、第三位字符“c”均不等，所以不需要做判断，图4的朴素算法步骤②③都是多余。

因为T的首位“a”与T第四位的“a”相等，第二位的“b”与第五位的“b”相等。而在①时，第四位的“a”与第五位的“b”已经与主串S中的相应位置比较过了，是相等的，因此可以断定，T的首字符“a”、第二位的字符“b”与S的第四位字符和第五位字符也不需要比较了，肯定也是相等的——之前比较过了，还判断什么，所以④⑤这两个比较得出字符相等的步骤也可以省略。


也就是说，对于在子串中有与首字符相等的字符，也是可以省略一部分不必要的判断步骤。如图5所示，省略掉右图的T串前两位“a”与“b”同S串中的4、5位置字符匹配操作。

对比这两个例子，我们会发现在①时，我们的i值，也就是主串当前位置的下标是6，②③④⑤，i值是2、3、4、5，到了⑥，i值才又回到了6。即我们在朴素的模式匹配算法中，主串的i值是不断地回溯来完成的。而我们的分析发现，这种回溯其实是可以不需要的——正所谓好马不吃回头草，我们的KMP模式匹配算法就是为了让这没必要的回溯不发生。

既然i值不回溯，也就是不可以变小，那么要考虑的变化就是j值了。通过观察也可发现，我们屡屡提到了T串的首字符与自身后面字符的比较，发现如果有相等字符，j值的变化就会不相同。也就是说，这个j值的变化与主串其实没什么关系，关键就取决于T串的结构中是否有重复的问题。
比如图3中，由于T=”abcdex”，当中没有任何重复的字符，所以j就由6变成了1。而图5中，由于T=”abcabx”，前缀的“ab”与最后“x”之前串的后缀“ab”是相等的。因此j就由6变成了3。
因此，我们可以得出规律，j值的多少取决于当前字符之前的串的前后缀的相似度。

我们把T串各个位置的j值的变化定义为一个数组next，那么next的长度就是T串的长度。于是我们可以得到下面的函数定义：

next数组值推导

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

  • 1.T=”abcdex”

j 123456
模式串T abcdex
next[j] 011111

1）当j=1时，next[1]=0；
2）当j=2时，j由1到j-1就只有字符“a”，属于其他情况next[2]=1；
3）当j=3时，j由1到j-1串是“ab”，显然“a”与“b”不相等，属其他情况，next[3]=1；
4）以后同理，所以最终此T串的next[j]为011111。

  • 2.T=”abcabx”

j 123456
模式串T abcabx
next[j] 011123

1）当j=1时，next[1]=0；
2）当j=2时，同上例说明，next[2]=1；
3）当j=3时，同上，next[3]=1；
4）当j=4时，同上，next[4]=1；
5）当j=5时，此时j由1到j-1的串是“abca”，前缀字符“a”与后缀字符“a”相等（前缀用下划线表示，后缀用斜体表示），因此可推算出k值为2（由‘p1…pk-1’=‘pj-k＋1…pj-1’，得到p1=p4）因此next[5]=2；
6）当j=6时，j由1到j-1的串是“abcab”，由于前缀字符“ab”与后缀“ab”相等，所以next[6]=3。

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

  • 3．T=”ababaaaba”

j 123456789
模式串T ababaaaba
next[j] 011234223

1）当j=1时，next[1]=0；
2）当j=2时，同上next[2]=1；
3）当j=3时，同上next[3]=1；
4）当j=4时，j由1到j-1的串是“aba”，前缀字符“a”与后缀字符“a”相等，next[4]=2；
5）当j=5时，j由1到j-1的串是“abab”，由于前缀字符“ab”与后缀“ab”相等，所以next[5]=3；
6）当j=6时，j由1到j-1的串是“ababa”，由于前缀字符“aba”与后缀“aba”相等，所以next[6]=4；
7）当j=7时，j由1到j-1的串是“ababaa”，由于前缀字符“ab”与后缀“aa”并不相等，只有“a”相等，所以next[7]=2；
8）当j=8时，j由1到j-1的串是“ababaaa”，只有“a”相等，所以next[8]=2；
9）当j=9时，j由1到j-1的串是“ababaaab”，由于前缀字符“ab”与后缀“ab”相等，所以next[9]=3。

  • 4．T=”aaaaaaaab”

j 123456789
模式串T aaaaaaaab
next[j] 012345678

1）当j=1时，next[1]=0；
2）当j=2时，同上next[2]=1；
3）当j=3时，j由1到j-1的串是“aa”，前缀字符“a”与后缀字符“a”相等，next[3]=2；
4）当j=4时，j由1到j-1的串是“aaa”，由于前缀字符“aa”与后缀“aa”相等，所以next[4]=3；
5）……
6）当j=9时，j由1到j-1的串是“aaaaaaaa”，由于前缀字符“aaaaaaa”与后缀“aaaaaaa”相等，所以next[9]=8。

KMP模式匹配算法实现

计算出当前要匹配的串T的next数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*  通过计算返回子串T的next数组。  */
void  get_next(String  T,  int  *next)
{
	int  i,  j;
	i  =  1;j  =  0;next[1]  =  0;
	/*  此处T[0]表示串T的长度  */
	while  (i  <  T[0])                                      
	{
		/*  T[i]表示后缀的单个字符，  */
		/*  T[j]表示前缀的单个字符  */
		if  (j  ==  0  ||  T[i]  ==  T[j])        
		{
			++i;++j;
			next[i]  =  j;
		}
		else	j  =  next[j];/*  若字符不相同，则j值回溯  */                          
	}
}

T = “abcabx”;
i=1; j=0;
next[1] = 0;
T[0] = 6

i=2; j=1;
next[2] = 1

j=0;//回溯

i=3; j=1;
next[3] = 1;

j=0;//回溯

i=4; j=1;
next[4] = 1;

i=5; j=2;
next[5] = 2;

i=6; j=3;
next[6]=3;

next = [0,1,1,1,2,3]
/———-/
T=”ababaaaba”

i=1;j=0;
next[1]=0;

T[0] = 9;

i=2;j=1;
next[2]=1;

j=next[1]=0;//回溯

i=3;j=1;
next[3]=1;

i=4;j=2;
next[4]=2;

i=5;j=3;
next[5]=3;

i=6;j=4;
next[6]=4;

j=next[4]=2;//回溯

j=next[2]=1;//回溯

i=7,j=2;
next[7]=2;

j=next[2]=1;//回溯

i=8;j=2;
next[8]=2;

i=9;j=3;
next[9]=3;

next[0,1,1,2,3,4,2,2,3]

KMP模式匹配算法实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*  返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。  */
/*  T非空，1≤pos≤StrLength(S)。  */
int  Index_KMP(String  S,  String  T,  int  pos)
{
	/*  i用于主串S当前位置下标值，若pos不为1，  */
	/*  则从pos位置开始匹配  */
	int  i  =  pos;                                              
	/*  j用于子串T中当前位置下标值  */
	int  j  =  1;                                                  
	/*  定义一next数组  */
	int  next[255];                                          
	/*  对串T作分析，得到next数组  */
	get_next(T,  next);                                  
	/*  若i小于S的长度且j小于T的长度时，  */
	/*  循环继续  */
	while  (i  <=  S[0]  &&  j  <=  T[0])          
	{
		/*  两字母相等则继续，相对于朴素算法增加了  */
		/*  j=0判断  */
		if  (j  ==  0  ||  S[i]  ==  T[j])        
		{
			++i;++j;
		}
		else/*  指针后退重新开始匹配  */                                                      
		{
			/*  j退回合适的位置，i值不变  */
			j  =  next[j];                              
		}
	}
	if  (j  >  T[0])	return  i  -  T[0];
	else	return  0;
}

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

KMP模式匹配算法改进

后来有人发现，KMP还是有缺陷的。比如，如果我们的主串S=”aaaabcde”，子串T=”aaaaax”，其next数组值分别为012345，在开始时，当i=5、j=5时，我们发现“b”与“a”不相等，如图5-7-6的①，因此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函数进行了改良。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*  求模式串T的next函数修正值并存入数组nextval  */
void  get_nextval(String  T,  int  *nextval)
{
	int  i,j;
	i  =  1;
	j  =  0;
	nextval[1]  =  0;
	/*  此处T[0]表示串T的长度  */
	while  (i  <  T[0])                                                
	{
		/*  T[i]表示后缀的单个字符，  */
		/*  T[j]表示前缀的单个字符  */
		if  (j  ==  0  ||  T[i]  ==  T[j])                  
		{
			++i;++j;

			/*  若当前字符与前缀字符不同  */
			if  (T[i]  !=  T[j])
			{
				/*  则当前的j为nextval在i位置的值  */
				nextval[i]  =  j;
			}
	        else
			{
				/*  如果与前缀字符相同，则将前缀  */
				/*  字符的nextval值赋值给nextval在i位置的值  */
				nextval[i]  =  nextval[j];
			}        
		}
		else	j  =  nextval[j];/*  若字符不相同，则j值回溯  */                                  
	}
}

nextval数组值推导

  • 1．T=”ababaaaba”

j 123456789
模式串T ababaaaba
next[j] 011234223
nextval[j] 010104210

先算出next数组的值分别为011234223，然后再分别判断。

1）当j=1时，nextval[1]=0；
2）当j=2时，因第二位字符“b”的next值是1，而第一位就是“a”，它们不相等，所以nextval[2]=next[2]=1，维持原值。
3）当j=3时，因为第三位字符“a”的next值为1，所以与第一位的“a”比较得知它们相等，所以nextval[3]=nextval[1]=0；如图所示。

4）当j=4时，第四位的字符“b”next值为2，所以与第二位的“b”相比较得到结果是相等，因此nextval[4]=nextval[2]=1；如图所示。

5）当j=5时，next值为3，第五个字符“a”与第三个字符“a”相等，因此nextval[5]=nextval[3]=0；
6）当j=6时，next值为4，第六个字符“a”与第四个字符“b”不相等，因此nextval[6]=4；
7）当j=7时，next值为2，第七个字符“a”与第二个字符“b”不相等，因此nextval[7]=2；
8）当j=8时，next值为2，第八个字符“b”与第二个字符“b”相等，因此nextval[8]=nextval[2]=1；
9）当j=9时，next值为3，第九个字符“a”与第三个字符“a”相等，因此nextval[9]=nextval[3]=0。

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

总结回顾

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