串，即字符串（String）是由零工或多个字符组成的有限序列。
逻辑结构：串是一种特殊的线性表，数据元素呈线性关系。
2.串的基本操作- StrAssign(&T，chars)：赋值操作。把串T赋值为chars。StrCopy(&T，S)：复制操作。由串S赋值得到串T。StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE。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
//串的顺序存储
//静态数组实现（定长顺序存储）
#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)); //用完需手动free
S.length = 0;
3.2链式存储
//串的链式存储
//存储密度低：每个字符1B，每个指针4B
typedef struct StringNode{
char ch; //每个结点存1个字符
struct StringNode *next;
}StringNode, *String;
//存储密度提高
typedef struct StringNode{
char ch[4]; //每个结点存多个字符
struct StringNode *next;
}StringNode,*String;
4.串的基本操作的实现
4.1 求子串
SubString(&Sub，S，pos，len)：求字串。用Sub返回串S的第pos个字符长度为len的子串。
//求子串
int SubString(SString &Sub, SString S, int pos, int len){
//子串范围越界
if(pos+len-1 > S.length)
return 0;
for(int i=pos; i<=pos+len-1; i++){
Sub.ch[i-pos+1] = S.ch[i];
}
Sub.length = len;
return 1;
}
4.2 比较操作
StrCompare(S，T)：比较操作。若S>T，则但会值>0；若S=T，则返回值=0；若S Index(S，T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置，否则返回函数值为0。 原理：利用下标一一匹配。 若模式串长度为m，主串长度为n，则 匹配成功的最好时间复杂度：O(m) 匹配失败的最好时间复杂度：O(n-m+1) = O(n-m) ≈ O(n) 匹配成功/失败的最坏时间复杂度：O((n-m+1)*m) ≈ O(nm) 前缀：除最后一个字符以外，字符串的所有头部子串 'a’的前缀和后缀都为空集，最长相等前后缀长度为0。'ab’的前缀为{a}，后缀为{b}，{a}∩{b}=空集，最长相等前后缀长度为0。'abc’的前缀为{a，ab}，后缀为{c，bc}，{a，ab}∩{c，bc}=空集，最长相等前后缀长度为0。'abca’的前缀为{a，ab，abc}，后缀为{a，ca，bca}，{a，ab，abc}∩{a，ca，bca}={a}，最长相等前后缀长度为1。'abcac’的前缀为{a，ab，abc，abca}，后缀为{c，ac，cac，bcac}，{a，ab，abc，abca}∩{c，ac，cac，bcac}=空集，最长相等前后缀长度为0。
将部分匹配值写为数组形式，就得到了部分匹配值的表： 下面用PM表来进行字符匹配： 发现 c 与 a 不匹配，前面的两个字符’ab’是匹配的，查表可知，最后一个匹配字符 b 对应的部分匹配值为0，因此按照下面的公式算出子串需要向后移动的位数： 发现 c 与 b 不匹配，前面的四个字符’abca’是匹配的，最后一个匹配字符a对应的部分匹配值为1，4-1=3，将子串向后移动3位，进行第三趟匹配。 子串全部比较完成，匹配成功。整个过程中，主串始终没有回退，故KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配，大大提高了匹配效率。 失配后移动情况 直接移动到合适位置 KMP算法就是在失配后可以直接移动到合适位置 已知：右移位数 = 以匹配的字符数 - 对应的部分匹配值 我们注意到： 这样，上式可以改写为：Move = (j-1) - next[j] 有时为了公式更加简洁、计算简单，将next数组整体加1。 最终得到：j = next[j]。 当第 j 个字符匹配失败时，由前1~j-1个字符组成的串记为S，则： 当子串和模式串不匹配时，主串指针 i 不回溯，模式串指针 j = next[j]，算法平均时间复杂度：O(m+n) 前面定义的next数组在某些情况下尚有缺陷，还可以进一步优化。模式’aaaab’在和主串’aaabaaaab’进行匹配时： 这个例子中，'a’与’b’不匹配时，'b’会继续与该’a’前的’a’匹配，这显然是不合理的。 nextval[]数组的代码： KMP算法只需将next换位nextval即可。//比较操作
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;
}
4.3 定位操作
//定位操作
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; //S中不存在与T相等的子串
}
5.串的朴素匹配算法
//朴素模式匹配算法
int Index(SString S, SString T){
int k=1; //k指向S
int i=k;
int j=1; //j指向T
while(i<=S.length && j<=T.length){
if(S.ch[i] == T.ch[j]){
i++;
j++; //继续比较后继字符
}else{
k++; //检查下一个子串
i = k;
j = 1;
}
}
if(j > T.length)
return k;
else
return 0;
}
//朴素模式匹配算法（课本）
int Index(SString S, SString T){
int i=1; //i指向S
int j=1; //j指向T
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;
}
后缀：除第一个字符外，字符串的所有尾部子串
部分匹配值：字符串的前缀和后缀的最长相等前后缀
下面以’abcac’为例说明：编号 1 2 3 4 5 S a b c a c PM 0 0 0 1 0 主串 a b a b c a b c a c b a b
第一趟匹配过程
子串 a b c a c 主串 a b a b c a b c a c b a b 子串 a b c
移动位数 = 以匹配的字符数 - 对应部分匹配值
因为2 - 0 = 2，所以将子串向后移动2位，进行二趟匹配。主串 a b a b c a b c a c b a b 子串 a b c a c 主串 a b a b c a b c a c b a b 子串 a b c a c
某趟发生匹配失败时，如果对应的部分匹配值为0，那么表示以匹配相等序列中没有相等的前后缀，此时移动的位数最大，直接将子串的首字符移动到主串的第 i 个位置进行下一趟比较；如果以匹配相等序列中存在最大相等前后缀，那么将子串向右滑动到和该相等前后缀对应（这部分下一趟不需要对齐），让后从主串 i 位置进行下一趟比较。主串 a b a b c a b c a c b a b a b c a c a b c a c a b c a c a b c a c 主串 a b a b c a b c a c b a b a b c a c a b c a c
上面两张图片也解释了“移动位数=以匹配的字符数-对应的部分匹配值”，对应的部分匹配值不用再次进行比较，相当于主串的后缀和子串的前缀得到匹配。
写成：Move = (j-1) - PM(j-1) (子串和主串的下标都是从1开始的)
使用部分匹配值时，每当匹配失败，就去找它前一个元素的部分匹配值，这样使用起来有些不方便，所以将PM表右移一位，这样哪个元素匹配失败，直接看它自己的部分匹配值即可。
以上例中‘abcac’的PM表右移一位，就得到next数组编号 1 2 3 4 5 S a b c a c next -1 0 0 0 1
1）第一个元素向右移动以后空缺用-1填充，因为若是第一个元素匹配失败，则需要将子串向右移动一位，而不需要计算子串的移动位置。
2）最后一个元素在右移的过程中溢出，因为原来的子串中，最后一个元素的部分匹配值是下一个元素使用的，但显然已没有下一个元素，故可以舍去。
相当于将子串的比较指针回退到：j = j-Move = j-( (j-1) - next[j]) = next[j] + 1编号 1 2 3 4 5 S a b c a c next 0 1 1 1 2
next[j]的含义：在子串的第 j 个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较。
next[j] = S的最长前后缀长度 + 1
特别地，next[1] = 0
next[j]=1时，代表没有相同前后缀（即不匹配）。//求模式串T的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++;
//若pi=pj，则next[j+1]=next[j]+1
next[j+1] = j;
}else{
//否则令j=next[j]，循环继续
j = next[j];
}
}
}
6.4 KMP算法代码
//KMP算法
int Index_KPM(SString S, SString T){
int i=1, j=1;
int next[T.length+1];
get_next(T, next); //求模式串的next数组
while(i<=S.length && j<=T.length){
if(j==0 || ch[i]==T.ch[j]){
i++;
j++; //继续比较后继字符
}else{
j = next[j]; //模式串向右移动
}
}
if(j > T.length)
return i-T.length; //匹配成功
else
return 0;
}
a
主串 a a a b a a a a b 模式 a a a a b j 1 2 3 4 5 next[j] 0 1 2 3 4 nextval[j] 0 0 0 0 4
因此，我们使用递归，将next[j]修改为next[next[j]]，直至两个不在相等为止，更新后的数组命名为nextval。void get_nextval(String T, int nextval[]){
int i=1, j=0;
nextval[1] = 0;
while(i
