一、串

1.1 串的定义

串是由零个或多个任意字符组成的有限序列（内容受限的线性表），又名叫字符串。

一般记为s="a1a2......an"(n≥0)，其中S是串的名称，用双引号括起来的字符串序列是串的值，注意单引号不属于串的内容。ai(1≤i≤n)可以是字母、数字、或其他字符，i就是该字符在串中的位置。串中的字符数目n称为串的长度。
零个字符的串称为空串，它的长度为0。

其他一些名词解释：

空格串，是只包含空格的串，注意与空串区别，空格串有长度切不一定只有一个空格。
子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地包含子串的串称为主串。
子串在主串中的位置就是子串的第一个字符在主串中的序号。

1.2 串的比较

字符串在计算机种的大小取决于挨个比较字母的前后顺序。事实上，串的比较是通过组成串的的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。
计算机中的常用字符是使用标准的 ASCII 编码，更准确一点，由7位二进制数表示一个字符，总共可以表示128个字符。后来发现一些特殊符号的出现，128个不够用，于是扩展ASCII码由8位二进制数表示一个字符，总共可以表示256个字符，这已经足够满足以英语为主的语言和特殊符号进行输入、存储、输出等操作的字符需要了。可是，单我们国家就有除汉族外的满、回、藏、蒙古、维吾尔等多个少数民族文字，换作全世界估计要有成百上千种语言与文字，显然这256个字符是不够的，因此后来就有了 Unicode编码，比较常用的是由16位的二进制数表示一个字符，这样总共就可以表示216个字符，约是65万多个字符，足够表示世界上所有语言的所有字符了。当然，为了和 ASCII码兼容，Unicode的前256个字符与 ASCI 码完全相同。
所以如果我们要在C语言中比较两个串是否相等，必须是它们串的长度以及它们各个对应位置的字符都相等时，才算是相等。
对于字符串不相等时，对于大小判定的定义如下：

给定两个串：s="a1a2......an"，t="b1b2......bn",当且仅当a1=b1,a2=b2,...,an=bn时，我们任务s=t。
对于两个不相等串，s="a1a2......an"，t="b1b2......bn"，当满足以下条件之一时，s<t。
1. n < m，且ai=bi（i=1,2,......,n）。
  例如当s="hap",t="happy"，就有s<t。因为t比s多
2. 存在某个k≤min(m,n)，使得ai=bi(i=1,2,......,k-1)，ak<bk。
  例如当s=“happen”，t="happy"，因为两串的前4
  个字母均相同，而两串前4个字符相同，而两串第5个字母（k值），字母e的ASCII码是101，而字母y的ASCII码是121，显然e<y，所以s<t。
比较的实际生活应用：查字典。

1.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。
	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)。在串S的第pos个字符之前插入串T。
	StrDelete(S,pos,len)：串S存在，1≤pos≤StrLength(S)-len+1。从串s中删除第pos个字符起长度为len的字串。

endADT

在不同语言中对于串的基本操作会有不同的方法，因此实现上述操作方法时，就依据选择的编程语言的基本操作进行实现。

/*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;    /*则返回i值*/
		}
	}
	return 0;  /*若无子串与T相等，返回0*/
}

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

1.4 串的存储结构

串的存储结构也氛围顺序存储和链式存储。

1.4.1 串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。
通常会用\0的转义字符来代表字符串的结束，从而避免单独存储字符串长度。
但顺序存储存在两个字符串拼接、新串插入和字符串替换等操作可能使得串序列的长度超过了数组的长度MaxSize。
于是对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做“堆”。这个堆可由语言的动态分配函数malloc()和free()来管理。

1.4.2 串的链式存储结构

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

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

1.5 串的模式匹配算法

1.5.1 朴素的模式匹配算法

模式匹配：这种子串的定位操作通常称做串的模式匹配。
假设我们要从下面的主串 S="goodgoogke"中，找到 T="googe"这个子串的位置。我们通常需要下面的步骤。

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

简单来说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或者全部便利完成为止。
假设主串S和要匹配的子串T的长度存在S[0]与T[0]中。

/*返回子串里在主串S中第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;
}

最坏时间复杂度为O((n-m+1)*m)。
效率太低。

1.5.2 KMP模式匹配算法

KMP算法全称：克努特——莫里斯——普拉特算法

1.5.2.1 KMP 模式匹配算法原理

假设主串S="abcdefgab"，待匹配子串T="abcdex"，如果使用朴素算法，前5个字母，两个串完全相等，直到第6个字母，"f"与"x"不等。

接下来按照朴素模式匹配算法，流程是②③④⑤⑥。即主串S中当i=2、3、4、5、6时，首字符与子串T的首字符军不等。
对于要匹配的子串T来说，“abcdex”首字母“a”与后面的串“bcdex”中任意一个字符都不相等，也就是说，既然“a”不与自己后面的子串中任何一个字符相等，呢么对于①来说，前五位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2位到第五位字符相等。即②③④⑤⑥的步骤是多余的。
理解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]，因此保留这一步。

通过观察可以得知i值可以不回溯，只需要考虑j值，当T串的字符与自身后面的字符比较，发现有相等字符时，j的取值就会不同，也就是说j值的取值和主串没有关系，主要取决于子串T串中是否有重复的字符问题。
总结规律如下，j值的多少取决于当前字符之前的串的前后缀的相似度。
把T串各个位置的j值的变化定义为一个数组next，那么next的长度就是T串的长度。于是可以得到下面的函数定义：

1.5.2.2 next数值的推导

推导过程：

当j=1时，next[1]=0;
当j=2 时，j 由 1 到 j-1 就只有字符“a”，属于其他情况 next[2]=1;
当j=3 时，同上，next[3]=1;
当j=4 时，同上，next[4]=1;
当 j=5 时，此时j由1 到j-1 的串是“abca”，前缀字符“a”与后缀字符“a”相等(前缀用下划线表示，后缀用斜体表示)，因此可推算出k值为 2(由'p1...pk-1’=pi-k+1…pj-1’，得到p1=p4)因此 next[5]=2;
当j=6 时,j 由1 到j-1 的串是“abcab”，由于前缀字符“ab”与后缀“ab相等，所以 next[6]=3。

算法实现：

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

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。*/
/* T非空，1≤pos≤StrLength(s)。*/
int Index_KMP(String S, String T, int pos)
{
	int i = pos;  /*i 用于主串S当前位置下标值，若pos部不为1，则让那个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值不变,与朴素算法增加了j==next[j]*/
		}
	}
	if(j > T[0])
		return i-T[0];
	else
		return 0;
}

对于 get_ next 函数来说，若T的长度为 m，因只涉及到简单的单循环，其时间复杂度为 0(m)，而由于i值的不回溯，使得 index_KMP 算法效率得到了提高，while 循环的时间复杂度为 0(n)。因此，整个算法的时间复杂度为 0(n+m)。相较于朴素模式匹配算法的 0((n-m+1) * m)来说，是要好一些。

1.5.3 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[]的值，这是个很好的办法。因此我们对求 next 函数进行了改良。
假设取代的数组为 nextval，增加了加粗部分，代码如下:

void get_nextval(String T,int *nextval)
{
	int i,j;
	i=1;
	j=0;
	nextval[1]=0;
	while (i<T[0]) /*此处T[0]表示串T的长度*/
	{
		if(j==0 || T[])
		{
			++i;
			++j;
			if(T[1]!=T[j]) /*若当前字符和前缀字符不同*/
			{
				nextval[i]=j;  /*则当前的j为nextval在i位置的值*/
			}
			else
				nextval[i] = nextval[j];  /*如果与前缀字符的nextval值赋值给nextval在i位置的组*/
		}
		else
			j=nextval[j];    /*若字符不相同，则j值回溯*/
	}
	
}

1.5.3.1 nextval数组值推导

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]=1

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 的值。

【Data Structure】数据结构解构其五：串

一、串