目录
串，即字符串( String）是由零个或多个字符组成的有限序列。一般记为
其中，S是串名，单引号括起来的字符序列是串的值;可以是字母、数字或其他字符;串中字符的个数 n 称为串的长度。n =0时的串称为空串（用
表示）。
例:
S="Hello World!" T="wait wait wait baby"
一些概念：
| 名称 | 含义 | 举例 |
| 子串 | 串中任意个连续的字符组成的子序列。 | "wait w'，'baby’是串T的子串 |
| 主串 | 包含子串的串。 | T是子串 'baby' 的主串 |
| 字符在主串中的位置 | 字符在串中的序号。 | ‘o'在S中的位置是5第一次出现) |
| 子串在主串中的位置 |
子串的第一个字符在主串中的位置。 | 'World'在S中的位置为7 |
注意：位序从1开始排
串是一种特殊的线性表，数据元素之间呈线性关系。
串的对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）
串的基本操作，如增删改查等通常以子串为操作对象。
假设有串T=""，S="Who are you?”，W="are''
| StrAssign(&T,chars) | 赋值操作。把串T赋值为chars。 |
| StrCopy(&T,S) | 复制操作。由串s复制得到串T。 |
| StrEmpty(S) | 判空操作。若s为空串，则返回TRUE，否则返回FALSE。 |
| StrLength(S) | 求串长。返回串s的元素个数。 |
| ClearString(&S) | 清空操作。将s清为空串。 |
| DestroyString(&S) | 销毁串。将串s销毁（回收存储空间）。 |
| Concat(&T,S1,S2) | 串联接。用T返回由S1和S2联接而成的新串 |
| Index(S,T) | 定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置;否则函数值为0。 |
| StrCompare(S,T) | 比较操作。若S>T，则返回值>0;若S=T，则返回值=0﹔若S<T，则返回值<0。 |
#define MAXLEN 255 //预定义最大串长为255
//静态数组实现（定长顺序存储）
typedef struct{
char ch[MAXLEN]; //每个分量存储一个字符
int length; //串的实际长度
}SString;
//动态数组实现（堆分配存储）
typedef struct{
char *ch; //按串长分配存储区，ch指向串的基地址
int length; //串的长度
}HString;
HString s;
s.ch =(char *)malloc(MAXLEN * sizeof(char));
s.length = 0;
优点：字符的位序和数组下标相同。
方式一：每个结点存储一个字符
typedef struct StringNode{
char ch; //每个结点存储1个字符
struct StringNOde * next;
}StringNode,*String;方式二： 每个结点存储多个字符，没有字符的位置可以用'#'或'\0'补足
typedef struct StringNode{
char ch[4]; //每个结点存储多个字符
struct StringNode *next;
}StringNode,*String;
#define MAXLEN 255 //预定义最大串长为255
typedef struct{
char ch[MAXLEN]; //每个分量存储一个字符
int length; //串的实际长度
}SString;SubString(&Sub,S,pos,len)
求子串。用sub返回串S的第pos个字符起长度为len的子串。
//求子串
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++)
Sub.ch[i-pos+1] = S.ch[i];
Sub.length = len;
return true;
}StrCompare(S,T)
比较操作。若S>T，则返回值>o;若S=T，则返回值=0;若S<T，则返回值<0。
int StrCompare(SString S,SString T){
//从第一个字符开始比较，直到其中一个串的字符先被比较完
for(int i=1; i<=S.length &&i<=T.length; i++){
if(S.ch[i]!=T.ch[i]) //字符不相等
return S.ch[i]-T.ch[i]; //返回字符大小比较
}
//扫描过的所有字符都相同，则长度长的串更大
return S.length-T.length;
}Index(S,T)
定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置;否则函数值为0。
int Index(SString S,SString T){
int i=1,n=StrLength(S),m=StrLength(T); //Strlength(S)是求串长的操作
SString sub; //用于暂存子串
while(i<=n-m+1){ //n-m+1为所有子串的数目
SubString(sub,S,i,m); //取出一个子串（从i开始到m结束）
if(StrCompare(sub,T)!=0)
i++; //不相等，进行下一个子串的比较
else
return i; //相等，返回子串在主串中的位置
}
return 0; //S中不存在与T相等的子串
}字符串模式匹配∶在主串中找到与模式串相同的子串，并返回其所在位置。
子串：主串的一部分，一定存在
模式串：不一定能在主串中找到
逻辑：
设主串长度为n，模式串长度为m，将所有长度为m的子串依次与模式串对比（最多对比n-m+1个子串），直到找到一个完全匹配的子串或所有的子串都不匹配为止。
和上面实现的Index(S,T)函数一致，即是暴力解法。
int Index(SString S,SString T){
int i=1,n=StrLength(S),m=StrLength(T); //Strlength(S)是求串长的操作
SString sub; //用于暂存子串
while(i<=n-m+1){ //n-m+1为所有子串的数目
SubString(sub,S,i,m); //取出一个子串（从i开始到m结束）
if(StrCompare(sub,T)!=0)
i++; //不相等，进行下一个子串的比较
else
return i; //相等，返回子串在主串中的位置
}
return 0; //S中不存在与T相等的子串
}KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度为O(m+n)
首先根据模式串T求next数组出来。
对于模式串T ='abaabc'，可得出以下结论
当第6个元素匹配失败时，可令主串指针i不变，模式串指针j=3
当第5个元素匹配失败时，可令主串指针i不变，模式串指针j=2
当第4个元素匹配失败时，可令主串指针i不变，模式串指针j=2
当第3个元素匹配失败时，可令主串指针i不变，模式串指针j=1
当第2个元素匹配失败时，可令主串指针i不变，模式串指针j=1
当第1个元素匹配失败时，匹配下一个相邻子串,令j=0,i++,j++
并将这些放到next数组中
| next[0] | next[1] | next[2] | next[3] | next[4] | next[5] | next[6] |
| 0 | 1 | 1 | 2 | 2 | 3 |
结合代码逻辑进行处理
//当元素匹配失败时，i不变，j指向next[j]的值
if(S[i] != T[j]) j=next[j];
//当第1个元素匹配失败时，令j=0,i++,j++
if(j==0) {i++;j++ }int Index_KMP(SString S,SString T,int next[]){
int i=1,j=1;
while(i<=S.length && j<=T.length){
if(j==0 || S.ch[i]==T.ch[j] ){
++j;
++i; //继续比较后继字符
}
else
j = next[j]; //模式串向右移动
}
if(j>T.length)
return i-T.length; //匹配成功
else
return 0;
}不同之处在于，
朴素模式匹配算法在匹配失败时，主串指针i会疯狂回溯。
匹配失败时，主串指针i不回溯
next数组的作用：当模式串的第j个字符失配时，从模式串的第 next[j] 的继续往后匹配
对于任何模式串，next[1]为0 ，next[2]为1
其他next:在不匹配的位置前，划一条分界线，模式串一步一步向右移动，直到分界线之前“能对上”，或模式串完全跨过子串，此时j指向哪儿，next[j]的值就是哪儿
对于模式串“google”的next数组为
| next[0] | next[1] | next[2] | next[3] | next[4] | next[5] | next[6] |
| 0 | 1 | 1 | 1 | 2 | 1 |
练习1：
模式串：T=ababaa
| 序号j | 1 | 2 | 3 | 4 | 5 | 6 |
| 模式串 | a | b | a | b | a | a |
| next[j] | 0 | 1 | 1 | 2 | 3 | 4 |
举例：当匹配到第5个元素失败时，模式串向右移动，直到分界线之前的内容一致。此时j指向第3个字符，则next[ 5 ] 为3
练习2：
| 序号j | 1 | 2 | 3 | 4 | 5 |
| 模式串 | a | a | a | a | b |
| next[j] | 0 | 1 | 2 | 3 | 4 |
主要是对next数组进行优化，将next数组优化为nextval数组。
对练习1的next数组进行优化：
| 序号j | 1 | 2 | 3 | 4 | 5 | 6 |
| 模式串 | a | b | a | b | a | a |
| next[j] | 0 | 1 | 1 | 2 | 3 | 4 |
| nextval[j] | 0 | 1 | 0 | 1 | 0 | 4 |
举例解释：在匹配到第3个元素失败时，按next[j],j应该指向第1个元素，但我们可以知道第3个元素是a，匹配失败了，所以当 j 指向第一个元素时也会不匹配。所以，我们可以直接将其优化，去除这多余的一步，即当你在第3个元素匹配失败时，next的指向为和第3个元素相同的字符，则 j 的指向再回退一步，指向next[ 1 ]
练习2的优化：
| 序号j | 1 | 2 | 3 | 4 | 5 |
| 模式串 | a | a | a | a | b |
| next[j] | 0 | 1 | 2 | 3 | 4 |
| nextval[j] | 0 | 0 | 0 | 0 | 4 |
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]]
else
nextval[j] = next[j];
}