数据结构（三）——串

1. 串的定义和基本操作

本节内容很少，重点是串的模式匹配，所以对于串的定义和基本操作，我就简单提一些易错点。另外，串也是一种特殊的线性表，只不过线性表是可以存储任何东西，而串只能存储字符。除此以外，我们进行串的查找时，很少查找单个字符，一般情况下是进行子串查取。

1.1 串的定义

上面是串的定义，以及一些有关串的术语的定义。

但是有几个易错点需要指出：

串的长度是不包含两侧引号的，例如S=”hello world!”的长度是12，而非14。
在串里，空格也要占1位长度。例如S=“n h”的长度是3。另外，由空格组成的串叫空格串。
确定子串在主串中的位置，其实就是确定子串的第一个字符在主串中的位置。
查找串里某个字符的位置，从第一字符开始查找时，要从1开始查起，而不是从0开始查。

1.2 串的基本操作

串的基本操作全在上图，这里说下几个需要注意的点：

区分清空操作和销毁串：清空操作是将串中字符情况，但是串本身的存储位置还在。而销毁操作，是将整个串都给销毁，无法在原地址上找到该串，要想使用串需重新分配存储空间。
串连接操作，是将两个串拼凑在一起，这个时候可能需要开辟存储空间，所以如果程序里多次使用串连接操作，要使用易扩展的存储结构。
定位操作，要在主串里找到子串，涉及到了匹配算法，也是我们这一章的重点，后面会细讲。
比较操作，注意比较两个字符串，并不是谁长谁就大，而是从第一个字符开始一位一位进行比较，当出现两个字符不同的时候，哪个字符大，哪个字符串就大。例如S=”abcd”，M=”acb”，两个字符串第一位全是a，所以比较第二位，而b<c，所以M>S。若两个字符串相等，则两个字符串一定相同。注意，这里b<c，并不是按英语里的排序，而是在计算机对字母的编码大小，一般情况下，计算机对字母使用ASCLL码进行编码，而在ASCLL码表里b的二进制表示小于c的二进制表示，所以c>b。如果有不理解的地方可以去看看视频串的定义和基本操作

2. 串的存储结构

2.1 串的顺序存储

同线性表，串的顺序存储也有两种创建方式，一使用静态数组进行顺序存储。二使用动态数据进行顺序存储。

//静态数组创建存储空间
#define MaxSize 255 //定义串的最大长度
typedef struct {
	char ch[MaxSize];	//每个分量存储一个字符
	int length;			//串当前长度
}SString;

//动态数组创建存储空间
typedef struct {
	char* ch;		//定义ch指针，指向串首地址
	int length;		//串的长度
}HString;

在不同教材里顺序存储方式有所差别，以下给出4种方案，第一种方案在末尾使用int（不一定int，也可是其他数据类型）记录存储长度，这样更容易获得长度，且范围足够。第二种让ch[0]充当length，这样可以使字符的位序和数组下标相同，但是ch[0]仅有一个字节，表示最大长度为255，存储的长度有限。方案三在结尾以‘\0’结尾，没有length变量，这样每次获得长度就需要我们去遍历。第四种综合了第1种和第2种方案，所以也综合了1,2两种的优点，不出意外，我们接下来对于串的基本操作的实现，都基于第4种方案进行设计。

2.2 串的链式存储

这里可以看到，1个字符占1个存储空间，但是在一个32位系统里，一个指针占4个bit的存储空间。如果我们每个结点只存放一个字符，那就会有大量空间被浪费。所以我们可以采用一个存储结点放4个字符，这样可以平衡存储空间的利用。

//链式存储
typedef struct StringNode {
	//char ch;				//每个结点存放一个字符
	char ch[4];				//每个结点存放4个字符
	struct String* next;	//指向下一个结点
}StringNode, *String;

2.3 串的基本操作实现

串的基本操作在1.2已展示，由于串就是一种特殊的线性表，而前面的线性表、栈、队列等，我们已对增删改查、初始化、判空等基本操作进行反复书写，这里为了节省时间便展示几个重要的操作的程序设计。

2.3.1 求子串

求子串，就是将字符串里第i个位置起，将长度为len的子串给取出来。注意，我们上图里采用的是2.1里几种存储方法的第4种，所以数组下标为0的位置没有进行数据存储。

//求子串
bool SubString(SString& Sub, SString S, int pos, int len) {
	if (pos + len - 1 > S.length)			//判断字符串长度
		return false;
	for (int i = pos; i < pos + len; i++)	//从pos位置将len长度子串取出
		Sub.ch[i - pos + 1] = S.ch[i];
	Sub.length = len;
	return true;
}

2.3.2 字符串比较

字符串比较，从首位开始一位一位比较，如果出现两个字符串同一位置字符不同，则哪个字符大，哪个字符串就大；若相同，接着往下比较。若两个字符串被扫描的地方都一样，则谁长谁大。若完全一样，则相等。

//字符串比较，若S>T，则返回值>0;若S<T,则返回值<0；
int StrCompare(SString S, SString T) {
	for (int i = 0; i < S.length && i <= T.length; i++) {
		if (S.ch[i] != T.ch[i])			//判相等
			return S.ch[i] - T.ch[i];	//不相等返还S.ch[i] - T.ch[i]的值
	}
	return S.length - T.length;			//若数据匹配完，谁长谁大
}

2.3.3 求子串位置

这里我们可以使用这样一种思路，结合前面两种操作，从第1位每次从主串里取要求子串长度，然后与要求子串进行比较，相同则返回首位下标，不同则让主串里所取的位置往后移一位再进行取串比较的操作。通过这种思想，我们可以结合2.3.1和2.3.2，使用2.3.1取串，然后通过2.3.2比较。如果取到最后发现没有与要求子串相等的串，则说明该主串里不存在要求子串。

//求子串位置操作
int Index(SString S, SString T) {
	int i = 1, n = StrLength(S), m = StrLength(T);	//获取子串和主串长度
	SString sub;									//暂存子串
	while (i <= n - m + 1)
	{
		SubString(sub, S, i, m);					//取子串
		if (StrCompare(sub, T) != 0)				//判相等
			++i;									//不等进入下轮取串判等操作
		else										//相等返回串头下标
			return i;
	}
	return 0;
}

3. 朴素模式匹配算法

首先介绍两个概念——主串和模式串

主串：一组数据较长的字符串。

模式串：一组数据较少的字符串。

这里要区分子串和模式串，子串一定可以在主串里找到，而模式串不一定能在主串里找到。

字符串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

字符串匹配有两种算法，一种朴素匹配，一种KMP。

这里我们先介绍朴素模式匹配。

朴素模式匹配算法的具体过程如下，假设主串长度为n，模式串长度为m，m<n。则从主串第1个位置开始，取长度为m的子串，与模式串进行匹配，不相等，则将所取子串的首位向后移动一位，再进行取串，判相等操作。最多匹配n-m+1个子串。到这里，我们就会发现，所谓朴素模式匹配算法和我们前面2.3.3里所说的求子串方法一样，只不过这里出现了可能找不到的情况。

所以，联系前面的求子串算法，我们很容易写出如下的朴素模式匹配算法：

//朴素模式匹配算法
int Index(SString S,SString T){
    int i=1,j=1;						//定义主串与模式串的起始匹配位置
    while(i<=S.length && j<=T,length){
        if(S.ch[i] == T.ch[j]){			//如果两个串当前匹配位置相等，继续后移匹配
            ++i; ++j;
        }
        else{
            i=i-j+2;					//匹配失败，进行下一轮初始化待匹配状态
            j=1
        }
    }
    if(j>T.length)						//匹配结束以后，如果j大于模式串长，说明匹配成功
        return i>T.length;
    else
        return 0;						//j小于模式串长，匹配失败
}

为了更方便我们理解这个算法，这里以一个实例的匹配过程，作为演示，来进行算法详解。

首先，用i指向主串S的下标1的地方，j指向模式串T的下标为1的地方。从主串S里取出第一组与模式串T等长的子串，同时令i，j后移进行每一位判相等操作。从上图可以看到，当i=j=6时，两个串不相同，于是令j回到模式串T的数组下标为1的地方，但是i回到的应该是1的下一位，即数组下标为2的地方。这里，我们可以发现i每次回去的值等于i-j+2，即令当前S串中被匹配的长度i减去模式串S中被匹配的长度j，此时i会回到第一个匹配位的前一位，这时候加2即可令i指向第一个匹配位的下一位，也即下一个匹配子串的第一个位置。

接下来是第二个子串与模式串比较过程，可以发现两个串的第一位就不相同，于是i应指向3，即第三个子串的首位，而j仍然在模式串1的位置。

第三轮匹配，发现主串中第三个子串与模式串T相等，这个时候两者就相同，由于是判断一位相同，然后再移动到下一位，所以当我们的模式串最后一位也被判断相同时，此时j还会再加1，这时j的数值大于模式串T的数值，所以，我们可以用i-T.length>0来判断相等。

说完了算法以及算法的运行过程，就要谈论评价一个算法必不可少的东西——时间复杂度。

在朴素模式匹配算法里，假设模式串长m（即每次都要匹配m个字符），主串长n（要匹配n-m+1个串）：

最优的时间复杂度：第一次匹配m个字符就匹配成功，所以最快时间复杂度=O(m)。

最坏时间复杂度：最后一个串匹配，才匹配成功，则要匹配n-m+1次m个字符，即O(mn-m²+m)=O(mn)。

最后进行一个简短的思维图总结：

4. KMP算法

写在开头：这一部分我写的有点简陋，主要是因为这部分内容是串这一章的核心，讲清比较繁琐，我只能在我的基础上进行一些重点指出，这样不会浪费时间，也能帮助我复习，有问题的可以跳转看视频：KMP

4.1 KMP基础

在前面，我们学习的朴素匹配算法里，如果匹配失败，主串前进了m步，就要退回m-1步，模式串要将数据指针指向头部。这样有大量时间消耗在回溯的过程上，所以为了减少这种时间消耗，提出了KMP匹配算法。

KMP算法就是在主串回溯位置上做了手脚，我们可以通过特殊的方法，使主串不进行回溯，同时对模式串每次回溯的位置进行确定，从而减少过多回溯产生的时间消耗。比如在bababaccd里找babac，我们第一次匹配时，会发现babab和babac最后一位不相同，按照朴素匹配算法，我们会将两者指针都回溯到最初位置。但我们可以发现，不将主串回溯，将模式串回溯到babac里第二个b的位置，也可以实现匹配成功，所以这就是我们优化后的KMP算法，而KMP算法的核心就是要找到我们在模式串里匹配失败时，对应该位应回溯的位置。

接下来以一个匹配过程作为演示，来进行KMP的介绍：

模式串匹配在最后一位（第6位）没有匹配成功，此时j回溯到1位。

当j=5时发生了不匹配，此时将j回溯到2。

综上，当j=4,3,2,1时匹配失败都要回溯对应位置，我们将其总结如下。

这里我们可以采用一个数组将每个不匹配位置的j要回溯的数位统计下来。然后在匹配失败时，从数组里提取要回溯的位置。

注意：

(1)在第1位匹配失败，理论上应保持不变，但却让其回溯到0，这是为了更方便代码的实施，可以联系接下来的算法代码理解。

(2)在回溯时出现可能会出现多个回溯位都可以的情况，例如从主串ababababababc里匹配模式串abababac，第一次匹配时，在c的位置出现匹配出错，此时可回溯到ababab，也可以回溯到abab，还可以回溯到ab，出现这种情况，要选择最大前缀(前缀和后缀的知识在下面补充，但大家应该都有基础，这里应该可以理解什么是前缀什么是后缀)回溯，即选择最长的那个进行回溯。

(3)如果从主串abccabca里匹配模式串abca，会发现在第4个位置匹配失败，这个时候要回溯到模式串头再次匹配，实际上，第4位的a匹配失败，我们就已经可以知道开头a的匹配肯定失败，但计算机依然会进行一次运算，这就是KMP所存在的缺点，从这里就可以发现KMP也存在非最优解。

接下来就着重说一下KMP的核心，next数组（模式串回溯数组）怎么求。

4.2 next数组求解

在next数组求解前，先补充一下概念——串的前缀和串的后缀。

串的前缀：包含第一个字符，且不包含最后一个字符的子串。

串的后缀：包含最后一个字符，且不包含第一个字符的子串。

求next数组的公式：假设第j个字符匹配失败，由前1~j-1个字符组成的串记为S，则：next[j]=S的最长相等前后缀长度+1

接下来以一道练习题加深印象。

这里我仅以j=5举例，其余的大家可以自己算。

j=5，则S=4，在aaaa里的最长前后相等缀为aaa=aaa，所以next[5]=3+1=4。

另外，j=1和2时，不论模式串有多长，他们的最长相等前后缀都为0，而为了匹配算法，所以1特定为0。在手算时，为了节省时间，我们可以直接写next[1]=0，next[2]=1。

上面是书上给出的next[j]求解公式，方法并不唯一，大家也可以根据自己的理解写自己的推导公式。

4.3 KMP算法

说了半天，我们已经可以理解KMP算法的大致流程以及实现过程。接下来我们就可以对KMP算法进行代码书写以及性能分析。

//next数组求解
void get_next(SString T, int next[]) {
	int i = 1, j = 0;
	next[1] = 0;
	while (i<T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j]) {
			++i; ++j;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

这里next数组的算法求解可能有点难以理解（我就没理解），所以我找了一个视频讲解，大家没看懂想弄懂的可以看一下：KMP算法next数组代码讲解

//KMP匹配
int Index_KMP(SString S, SString T) {
	int i = 1, j = 0;
	int next[T.length+1];					//这里加1，是因为我们使用2.1里的第四种存储方法，数组首位空出
	get_next(T, next);						//求模式串T的next数组
	while (i<=S.length&&j<=T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j]) {
			++i; ++j;						//逐级匹配
		}
		else
			j = next[j];					//匹配失败
	}
	if (j > T.length)
		return i - T.length;				//匹配成功
	else
		return 0;							//匹配失败
}

在这里，求next数组，假设模式串长m，get_next的时间复杂度可以简单认为是O(m)。

假设主串的长度为n，则匹配过程的时间复杂度可以简单认为是O(n)。

KMP算法的时间复杂度就可以认为是O(m+n)。

这里的理解是比较粗糙的，实际上的计算过程可能要考虑很多且很复杂。不过大家记住这个结论就好。

上面是对KMP算法与朴素模式匹配算法的一个简短总结与比较。大家可以看一下。

4.4 KMP算法优化

在4.1的注意事项里的第三条，我们说过，如果出现匹配失败的位置上的字符与模式串回溯位置的字符相同，则会出现多匹配的情况，这里，我们就说一下如何解决这种情况。

如上图，我们在i=j=3的位置出现匹配失败，如果根据常规的next数组，此时next[3]=1，我们回溯到j=1的位置，显然j=1与i=3的位置仍会匹配失败，这次失败，我们就会将j=1处根据next数组再进行回溯。既然如此，我们为什么不在一开始就令next[3]=next[1]=0呢？

提到这里，很多人就可以想到KMP的优化思路，就是优化next数组，获得一个新的nextval数组。

这里说下我对nextval数组的理解，希望能帮助大家更好的理解。我对nextval数组的理解其实就是一个带前继的链表，这个表的前继里指向着串里字符的回溯数据位置，数据域里存放该位置字符。如果一个结点数据域里的字符与前继结点里的字符相等，则他的前继里所指向的最终位置应该是前一个结点的前继所指向的位置，如果前一个结点的前继所指向的位置里的数据域与前一个结点数据域里的值一样，则应该继续向前指向，直到前面数据里的值与后一个结点里的数据域值不一样，才算指到最终位置，而这个最终的位置，就是我们要回溯到的位置，也就是nextval数组里对应字符应回溯的位置。

根据上面所说，我们可以得到nextval数组的优化思路，先写出next数组，然后判断匹配失败j处的字符是否等于其next[j]里所指向回溯位置的字符，如果不相等，则其回溯位置，就是其求出的next数组所要回溯的位置，即nextval[j]=next[j]；如果相等，则其回溯位置，应与其next数组里所指的回溯位置的字符的最终回溯位置相同。

这里我们可以写出nextval求解算法：

nextval[1]=0;
for (int j=2 ; j<=T.length ; j++){
    if(T.ch[next[j]] == T.ch[j])			//当前位置字符与回溯位置字符相等
        nextval[j] = nextval[next[j]];		//nextval应等于回溯位置字符的nextval
    else									//不等
        nextval[j] = next[j];				//nextval就是next
}