串

1 串的定义2 串的存储结构2.1 定长顺序存储表示2.2 堆分配存储表示2.3 块链存储表示▲3 串的基本操作3.1 模式匹配3.1.1 依赖于其他串操作3.1.2 暴力匹配算法3.1.3 KMP算法3.1.4 改进的KMP算法（1）next数组（2）next数组改写（3）已知next[j]，获取next[j+1]（4）KMP匹配算法实现 3.1.5 KMP算法的进一步优化 4 参考

1 串的定义

串：由0个或多个字符组成的有限序列 $$S{=}^{\prime }{a}_1{a}_2\cdot \cdot \cdot a_n^{\prime }（n\ge 0)$$子串：串中任意个连续的字符组成的子序列

（1）前缀：除最后一个字符以外，字符串的所有头部子串； （2）后缀：除第一个字符以外，字符串的所有尾部子串； （3）部分匹配值：字符串的前缀和后缀的最长相等前后缀长度。

主串：包含子串的串空串$\varphi$：长度为0的串空格串：由1个或多个空格组成的串，不是空串串的长度$n$：串中字符的个数

串长的两种表示方法： （1）用一个额外的变量len来存放串的长度； （2）在串值后面加一个不计入串长的结束标记字符“\0”，此时串长为隐含值。

字符在串中的位置：某个字符在串中的序号两个串相等：长度相等且对应位置的字符相等

2 串的存储结构

2.1 定长顺序存储表示

【静态】用一组地址连续的存储单元存储串值的字符序列

/*定长数组*/ #efine MAXLEN 255 //预定义最大串长为255 typedef struct{ char ch[MAXLEN]; //每个分量存储一个字符 int length; //串的实际长度 }SString;

截断：串的实际长度只能 ≤ MAXLEN，超过预定义长度的串值会被舍去 克服截断：动态分配

2.2 堆分配存储表示

【动态】用一组地址连续的存储单元存储串值的字符序列

/*动态分配*/ typedef struct{ char *ch; //按串长分配存储区，ch指向串的基地址 int length; //串的长度 }HString;

自由存储区——“堆” malloc()函数：申请分配一块存储空间   若分配成功，则返回一个指向起始地址的指针   若分配失败，则返回NULL free()函数：释放已分配的空间

2.3 块链存储表示▲

块链结构：整个链表块：块链结构的每个结点每个结点既可以存放一个字符，也可以存放多个字符

3 串的基本操作

void StrAssign(String &T, String chars); //赋值操作。把串T赋值为chars int StrCompare(String S, String T); //比较操作。若S＞T，则返回值＞0； // 若S＝T，则返回值＝0； // 若S＜T，则返回值＜0。 int StrLength(Strirng S); //求串长。返回串S的元素个数 String Concat(String &T, String S1, Srting S2); //串联接。用T返回由S1和S2联接而成的新串 _Bool SubString(String &Sub, String S, int pos, int len); //求子串。用Sub返回串S的第pos个字符起长度为len的子串 _Bool StrCopy(String &T,String S); //复制操作。由串S复制得到串T _Bool StrEmpty(String S); //判空操作。若S为空串，则返回TRUE，否则返回FALSE int Index(String S,String T); //定位操作【模式匹配】。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0 //子串（模式串）在主串中的位置 _Bool ClearString(String &S); //清空操作。将S清为空串。 _Bool DestroyString(String &S); //销毁串。将串S销毁。

3.1 模式匹配

3.1.1 依赖于其他串操作

/*依赖于其他串操作*/ int Index(String S, String T) { int i = 1; int n = StrLength(S); int m = StrLength(T); while (i <= n - m + 1) { SubString(sub, S, i, m); if (StrCompare(sub, T) != 0) i++; else return i; //返回子串在主串中的位置 } return 0; //S中不存在与T相等的子串 }

3.1.2 暴力匹配算法

/*暴力匹配算法*/ int Index(SString S, SString T) { int i = 1, j = 1; while (i <= S.length && j <= T.length) { if (S.ch[i] == T.ch[i]) { i++; j++; //继续比较后继字符 } else { /*指针后退，重新开始匹配*/ i = (i - (j - 1)) + 1; //已经有j-1个字符匹配，第j个字符匹配不上 //先回溯i-(j-1)个字符【即本次匹配的起点】，再+1进行下一轮匹配 j = 1; } } if (j > T, length) return i - T.length; else return 0; }

3.1.3 KMP算法

$$部分匹配表PartialMatch，PM$$ 以子串’abcac’为例 部分匹配表为：

编号12345SabcacPM00010

分析过程：

子串前缀后缀前缀∩后缀部分匹配值a$\varphi$$\varphi$$\varphi$0ab{a}{b}$\varphi$0abc{a,ab}{c,bc}$\varphi$0abca{a,ab,abc}{a,ca,bca}{a}1abcac{a,ab,abc,abca}{c,ac,cac,bcac}$\varphi$0

子串右移位数 = 已匹配的字符数 - 最后一个匹配字符对应的部分匹配值

$$Move=(j-1)-PM[j-1]$$

3.1.4 改进的KMP算法

（1）next数组

$$next数组：PM表PM那一行右移一位$$

编号12345Sabcacnext-10001

$$Move=(j-1)-next[j]$$

注意

（1）第一个元素右移以后的空缺用-1填充 因为若是第一个元素匹配失败，则需要将子串向右移动一位，而不需要计算子串移动的位数。 （2）最后一个元素在右移的过程中溢出 因为原来的子串中，最后一个元素的部分匹配值是其下一个元素使用的，但显然已没有下一个元素，故可以舍去

此时，相当于将子串的比较指针j回退到 $$j=j-Move=next[j]+1$$

（2）next数组改写

因此next数组也可写为：

编号12345Sabcacnext01112 此时，j=next[j]

next[j]含义：在子串的第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较

$$next[j]=\{\begin{array}{ll}0,& \text{j=1}\\ max\{k|1<k<j且‘p_1\cdot \cdot \cdot p_{k-1}’=‘p_{j-k+1}\cdot \cdot \cdot p_{j-1}’\},& \text{当此集合不空时}\\ 1,& \text{其他情况}\end{array}$$

解释

（1）$next[1]=0$：当模式串中的第一个字符与主串的当前字符比较不相等时，模式串应右移一位，主串当前指针后移一位，再和模式串的第一字符进行比较。 （2）$next[j]=max\{k\}$：当主串的第i个字符与模式串的第j个字符失配时，主串$i$不回溯，则假定模式串的第$k$个字符与主串的第$i$个字符比较，即$k$为模式串的下次比较位置。 由于$k$值可能有多个，为了不使向右移动丢失可能的匹配，右移距离应该取最小，由于$j-k$表示右移距离，所以取$max\{k\}$。 （3）$next[其他情况]=1$：除上面两种情况外，发生失配时，主串指针i不回溯，在最坏情况下，模式串从第$1$个字符开始与主串的第$i$个字符比较。

（3）已知next[j]，获取next[j+1]

$next[1]=0$ 设$next[j]=k$

$next[j+1]$有两种情况：

若$p_k=p_j$： $$next[j+1]=next[j]+1$$若$p_k\ne p_j$ ：

$$next[j+1]=\{\begin{array}{ll}{k}^{\prime }+1且k^{\prime }=next[next...[k]]& \text{，1<k′<k<j}\\ 1& \text{，不存在k′，即不存在长度更短的相等前缀后缀}\end{array}$$

/*获取next*/ void get_next(String 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; //若pi=pj，则next[j+1]=next[j]+1 } else j = next[j]; //否则令j=next[j]，循环继续 } }

（4）KMP匹配算法实现

/*KMP算法*/ 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; }

3.1.5 KMP算法的进一步优化

思想：由于可能出现$p_j=p_{next[j]}$的情况（会出现多余的无意义的比较），将$next[j]$修正为$next[next[j]]$，直到两者不相等为止。

void get_nextval(String T, int nextval[]) { int i = 1, j = 0; nextval[1] = 0; while (i < T.length) { if (j == 0 || T.ch[i] == T.ch[j]) { ++i; ++j; if (T.ch[i] != T.ch[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } }

4 参考

王道