4.1串的定义和实现
4.1.1串的定义
串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为：S=′a1a2...an′(n>=0)S ='a_1a_2...a_n'(n>=0)S=′a1a2...an′(n>=0)
其中，S是串名，单引号括起来的字符序列是串的值；aia_iai可以是字母、数字或其他字符；串中字符的个数n称为串的长度。n=0n = 0n=0时的串称为空串（用∅表示）。
- 子串： 串中任意个连续的字符组成的子序列。
- 主串： 包含子串的串。
- 字符在主串中的位置：字符在串中的序号。<从1开始>
- 串是一种特殊的线性表，数据元素之间呈线性关系。
基本操作：
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联接而成的新串
SubString(&Sub,S,pos,len)： 求子串。用Sub返回串S的第pos个字符起长度为len的子串。
Index(S,T)： 定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
StrCompare(S,T)： 比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。
字符集：
任何数据存到计算机中一定是二进制数。
需要确定一个字符和二进制数的对应规则这就是“编码”
“字符集”：英文字符，ASCII字符集，中英文，Unicode字符集
基于同一个字符集，可以有多种编码方案，如：UTF-8，UTF-16
4.1.2串的存储结构
顺序存储
静态存储结构
#define MaxSize 255
//静态数组实现
typedef struct{
char ch[MaxSize];
int length; //串的实际长度
}SString;
//分配联讯存储空格，每个char字符占1B
动态存储结构
//动态数组实现
typedef struct{
char *ch; //按串长分配存储区，ch指向串的基地址
int length;
}HString;
链式存储
#define MaxSize 255
typedef struct StringNode{
char ch; //每个结点存储一个字符
struct StringNode *next;
}StringNode, * String;
//存储密度低，每个字符1B，每个指针4B
//块链存储
typedef struct StringNode{
char ch[4]; //每个结点存储多个字符
struct StringNode *next;
}StringNode, * String;
推荐第二种形式。
基本操作的实现：
定义：
#define MaxSize 255
//静态数组实现
typedef struct{
char ch[MaxSize];
int length; //串的实际长度
}SString;
求子串：
用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;
}
比较操作：
若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。
int StrCompare(SString S,SString T){
for(int i=1;i<=S.length;i++){
if(S.ch[i]!=T.ch[i])
return S.ch[i]-T.ch[i];
}
return S.length-T.length;
}
定位操作：
若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
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;
}
4.2串的模式匹配
4.2.1朴素模式匹配算法
核心思想： 暴力决解问题
主串长度为nnn,模式串长度为mmm
朴素模式匹配算法： 将主串中所有长度为mmm的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有子串都不匹配为止。<最多对比n−m+1n-m+1n−m+1个子串>
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)
return i-T.length;
else
return 0;
}
4.2.2KMP算法
由D.E.Knuth，J.H.Morris和V.R.Pratt提出，因此称为 KMP算法。
是对朴素模式匹配算法的优化。
优化的原理就是减少了i指针的回溯，通过已经计算好的next指针，提高算法的整体运行效率。
其中next数组记录了当第几个元素匹配失败时候，j的取值。
next数组只和短短的模式串有关，和长长的主串无关（重要）
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]){
++i;
++j; //继续比较后继字符
}else{
j=next[j]; //模式串向右移动
}
}
if(j>T.length)
return i-T.length; //匹配成功
else
return 0;
}
求next数组：
- 任何模式串都一样，第1个字符不匹配时，只能匹配下一个子串，因此next[1]都无脑写 0
- 任何模式串都一样，第2个字符不匹配时，应尝试匹配模式串的第1个字符，因此next[2]都无脑写 1
至于具体需根据实际字符串才能进行求解。
next[j]={0,j=1max{k∣1<k<j 且 p1⋯pk−1=pj−k+1⋯pj−1},当此集合非空时1,其他情况 \text{next}[j] = \begin{cases} 0, & j=1 \\\\ \max \left\{ k \mid 1 < k < j \text{ 且 } p_1 \cdots p_{k-1} = p_{j-k+1} \cdots p_{j-1} \right\}, & \text{当此集合非空时} \\\\ 1, & \text{其他情况} \end{cases} next[j]=⎩ ⎨ ⎧0,max{k∣1<k<j 且 p1⋯pk−1=pj−k+1⋯pj−1},1,j=1当此集合非空时其他情况
KMP算法进一步优化：
nextval数组是对next数组的进一步优化，即判断下一步的字符是否与本次字符相等，如果相等用nextval替代next数组，减少了无意义的对比。
nextval数组求法：
for(int j=2;j<=T.length;j++)
{
//让第next值个元素的值和当前元素比较
if(T.ch[next[j]]==T.ch[j])
//若相等则让第next值个元素的nextval值复制给当前元素的nextval值
nextval[j] = nextval[next[j]];
else
//若不等则让当前元素的next值赋值给当前元素的nextval值
nextval[j] = next[j];
}