@[toc]
本篇将讲述串的相关内容。
在前面，我们学习了线性表、栈和队列，接下来我们继续学习串、数组和广义表的相关内容。
对于串，学过字符串的同学应该都不陌生，而C语言中没有字符串类型，是通过字符数组实现的，字符串的一些基本操作，比如分割字符串、求字符串长度等都是通过操作字符数组实现的，C语言之后的一些高级语言都自己封装了字符串类型。
那么首先就来了解一下C语言中的串。
串的定义
串是由零个或多个任意字符组成的有序序列
s = "a1a2...an"(n≥0)，其中s为串名，引号部分为串值，n为串长。当n = 0时，称s为空串，通常用符号∅表示。
串的相关概念
- 子串：一个串中任意个连续字符组成的子序列(含空串)称为该串的子串。例如，"h"，"hello"，"world"，"w"，"wor"，"ld"，都是"helloworld"的子串
- 主串：包含子串的串称为主串
- 字符位置：字符在字符序列中的序号
- 子串位置：子串第一个字符在主串中的位置
- 空格串：由一个或多个空格组成的串，与空串不同
- 串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的
串的抽象数据类型定义
到现在为止，关于串的抽象数据类型定义相信大家都能够自己写出来，我就直接贴出来了：
ADT String{
数据对象：D = {
ai|ai∈CharacterSet,i = 1,2,...,n-1,n,n≥0}
数据关系：R = {
<ai-1,ai>|ai-1,ai∈D,i = 1,2,...,n-1,n}
基本操作：
StrAssign(&T,chars);//串赋值
StrCompare(S,T);//串比较
StrLength(S);//求串长
Concat(&T,S1,S2);//串连接
SubString(&Sub,S,pos.len);//求子串
StrCopy(&T,S);//串拷贝
......
}ADT String
关于串的操作非常多，我就不全部写出来了。
串的存储结构
串的结构和线性表相同，所以串可以采用与线性表相同的存储结构，我们同样介绍以下两种存储结构：
- 顺序存储结构
- 链式存储结构
串的顺序存储结构
串的顺序存储结构定义如下：
#define MAXSIZE 10
typedef struct{
char ch[MAXSIZE + 1];//字符数组，表示串
int length;//串长
}String;
在声明字符数组的时候通常会在原数组大小上加1，至于为什么这样做放到后面说。
串的链式存储结构
串的链式存储结构同样通过结点生成一个链表，每个结点存储对应的结点，如下图所示：
链表的优点显而易见，操作方便，存取快速，但是缺点也很大，存储密度太低，一个char类型的字符就要占用一个结点的内存。
办法总比困难多，为了解决链表存储密度低的问题，可以在一个结点里存储多个字符，充分利用空间，如下图所示：
所以通常我们使用的都是第二种链式结构，我们称其为块链。
串的块链结构定义如下：
#define MAXSIZE 100
typedef struct Chunk{
char ch[MAXSIZE];
struct Chunk *next;
}Chunk;
typedef struct{
Chunk *head; //串的头指针
Chunk *tail; //串的尾指针
int length; //串的长度
}String;
正常情况下，对串的操作仅限于查找，插入和删除操作很少，所以一般我们采用串的顺序存储结构实现。
串的基本操作
下面介绍串的一些基本操作。
串的模式匹配算法
如何确定子串在主串中的位置，称为串的模式匹配。
下面介绍两种串的模式匹配算法：
- BF算法
- KMP算法
BF算法
先介绍BF算法，BF是Brute-Force的简称，意思是简单的匹配算法，采用的是暴力比较的办法，算法思想是从主串中的第一个字符开始，依次与子串比较，直至成功匹配。
假设有这样的一个主串：aaaabc，要在该串中查找子串aaab的位置，该如何查找呢？
BF算法是这样实现的：
先定义两个游标i、j，i用于遍历主串，j用于遍历子串，从主串的第一个字符开始，与子串的第一个字符进行比较：
又匹配成功了，让```i+1=3```，```j+1=3```，继续比较：
还是匹配成功，接着让```i+1=4```，```j+1=4``，继续比较：
```a```与```b```不匹配，此时就不用继续比较了，让主串从第二个字符开始重新与子串进行匹配，可是现在i = 4，j = 4，该如何让游标退回去呢？
子串游标很简单，让j = 1，重新开始就可以了，如何让主串游标从下一个字符开始呢？
可以这样做，先让i - j，结果就等于0，然后结果加1，即：```i - j + 1```表示的是上一次开始比较的位置，那我们让结果再加1，即：```i - j + 2```表示的就是下一个开始比较的字符位置。
这样我们又重新开始比较了，主串的第二个字符和子串的第一个字符进行比较：
匹配成功，i加1等于3，j加1等于2，继续比较：
匹配成功，i加1等于4，j加1等于3，继续比较：
匹配成功，i加1等于5，j加1等于4，继续比较：
匹配成功，i加1等于6，j加1等于5，此时匹配成功，就返回主串中子串的第一个字符的序列，用i的值减去子串的长度即可得到。
BF代码实现如下：
```c
int Index_BF(String s,String 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){
return i - t.length;
}else{
return 0;
}
}
关于在定义时数组大小加1的问题，就是为了方便游标位置的思考，让游标从1开始，符合人的正常思维。
KMP算法
由于BF算法效率低下，克努特、莫里斯和普拉特三人共同提出了KMP算法，该算法较BF算法有了很大的改进，效率显著提高。
KMP算法思想：利用已经部分匹配的结果加快模式串的滑动速度，且主串的游标不必回溯。
假设有主串ababcabcacbab，子串abcac，要想查找子串位置，KMP算法步骤如下：
定义两个游标i和j，i表示主串游标，j表示子串游标，初始让i和j都等于1，第一次是主串和子串的首字符比较：
匹配成功，i和j均加1，继续比较：
匹配成功，i和j均加1，继续比较：
匹配失败，如果是BF算法，此时i和j都得回溯，i回溯到主串的第二个字符位置，j则从子串的第一个字符重新开始。但是KMP算法不这样，为了提高效率，它并不打算回溯，而是让游标i从主串中匹配失败的位置继续匹配，但是得让j回到子串的初始位置，然后开始比较：
匹配成功，i和j均加1，接着一直进行比较，直到匹配失败：
这个时候i不必回溯，它仍然从b开始，但是此时的j不再是从子串的初始位置开始比较了，因为串尾字符的前一个字符和串首的字符相同，且已经匹配成功，所以我们只需将j回溯到子串的第二个位置即可，然后进行比较：
匹配成功，算法就结束了。
通常，我们会定义next[j]数组，表明当子串中第j个字符与主串中相应字符匹配失败时，在子串中需要重新和主串中该字符进行比较的字符的位置。
我们需要在子串找到串尾的前缀和后缀，如果串尾的前缀和j前面的若干字符相等的话，就可以获得k的值，当然k的值可能不止一个，我们就找到其中的最大值即可。如果没有找到相等的情况，且j = 1时，就让k的位置为1，其它情况为0。总结如下：
$$ next[j] = \begin{cases} max\lbrace k_i 1
这样很难理解，我们举个例子，比如下面的一个子串：
下面开始计算：
- 先看子串的第一个字符a，此时j = 1，所以next[j]=0
- 再看子串的第二个字符b，字符b只有一个前缀a，属于其它情况，所以next[j]=1
- 再看子串的第三个字符c，字符c的前缀b与前面开始的a不相等，属于其它情况，所以next[j]=1
- 再看子串的第四个字符a，字符a的前缀c与开始位置的a不相等，属于其它情况，所以next[j]=1
- 再看子串的第五个字符a，字符a的前缀a与开始位置的a相等，当然还要比较组合字符，字符a的前缀ca与开始位置的ab不相等，因为
k - 1 = 1，所以next[j]=2 - 再看子串的第六个字符b，字符b的前缀a与开始位置的a相等，然后比较组合字符，字符b前缀aa与开始位置的ab不相等，字符b的前缀caa与开始位置abc不相等，所以next[j]=2
- 再看子串的第七个字符b，字符b的前缀b与开始位置的a不相等，继续比较组合字符，字符b的前缀ab与开始位置的ab相等，字符b的前缀aab与开始位置的abc不相等，字符b的前缀caab与开始位置的abca不相等，字符b的前缀bcaab与开始位置的abcaa不相等，所以next[j]=2
- 后面的就不一一分析了，分析流程相信大家已经清楚了吧
代码实现如下：
void get_next(String str, int *next){
//求模式串str的next数组
int i = 1,j = 0;
next[0] = str.length;
next[1] = 0;
while(i < str.length + 1){
if(j==0 || str.ch[i] == str.ch[j]){
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
}
int Index_KMP(String s, String t, int *next){
int i=1,j=1;
while(i <= s.length && j <= t.length){
if(j == 0 || s.ch[i] == t.ch[j]){
++i;
++j;
}
else{
j = next[j];
}
}
if(j > t.length)
return i - t.length;
else
return 0;
}
KMP算法的关键就是求出子串的next数组。
源代码
文章中的所有代码：
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MAXSIZE 100
typedef struct{
char ch[MAXSIZE + 1];//字符数组，表示串
int length;//串长
}String;
void get_next(String str, int *next){
//求模式串str的next数组
int i = 1,j = 0;
next[0] = str.length;
next[1] = 0;
while(i < str.length + 1){
if(j==0 || str.ch[i] == str.ch[j]){
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
}
int Index_KMP(String s, String t, int *next){
int i=1,j=1;
while(i <= s.length && j <= t.length){
if(j == 0 || s.ch[i] == t.ch[j]){
++i;
++j;
}
else{
j = next[j];
}
}
if(j > t.length)
return i - t.length;
else
return 0;
}
int Index_BF(String s,String 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){
return i - t.length;
}else{
return 0;
}
}
