串是有零个或多个字符组成的有限序列，又名字符串。

5.1 开场白

枯眼望遥山隔水，往来曾见几心知？壶空怕酌一杯酒，笔下难成和韵诗。途路阻人离别久，讯音无雁寄回迟。孤灯夜守长廖寂，夫忆妻兮父忆儿。

5.2 串的定义

串是有零个或多个字符组成的有限序列，又名字符串。 一般记为 s = “a1a2……an”。串中的字符数目n称为串的长度。零个字符的串称为空串。

5.3 串的比较

　　串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。 　　计算机中的常用字符使用ASCII编码（7位二进制数表示128个字符）。Unicode编码（16位二进制数表示， 216 ,约是6.5万个字符）足够表示世界上所有语言的字符了，为了与ASCII码兼容，Unicode的前256个字符与ASCII码完全相同。 　　给定两个串：s = “ a1a2...an ”， t = “ b1b2...bn ”，当满足以下条件之一时，s < t.

n < m，且 ai=bi （i=1,2，… ，n）。存在某个k <= min(m, n),使得 ai=bi （i=1,2，… ，k-1）， ak<bk 。

5.4 串的抽象数据类型

串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集。因此对于串的基本操作同样线性表有很大差别的。线性表更关注的是单个元素的操作，但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作。

ADT 串 Data 串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。 Operation StrAssign（T, *chars）：生成一个其值等于字符串常量chars的串T。 StrCopy（T, S）：串S存在，由串S复制得到得到串T。 ClearString（S）：串S存在，将串清空。 StringEmpty（S）：若串为空，返回true，否则返回false。 StrLength(S):返回串S的元素个数，即串的长度。 StrCompare（S,T）：若S>T,返回值>0,若s=T，返回0，若s<T,返回值<0. Concat(T,S1，S2)：用T返回由S1和S2联接而成的新串。 SubString（Sub，S，pos，len)：串S存在，1<=pos<=StrLength(S)，且0<=len<=StrLength(S)-pos+1,用Sub返回串中S的第pos个字符起长度为len的子串。 Index(S,T,pos)：串S和T存在，T是非空串，1<=pos<=StrLength(S).若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0； Replace(S,T,V)：串S、T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串。 StrInsert（S,pos，T）：串S和T存在，1<=pos<=StrLength(S)+1.在串S的第pos个字符之前插入串T。 StrDelete（S，pos，len）：串s存在，1<=pos<=StrLength(S)-len+1.从串S中删除第pos个字符起长度为len的子串。 endADT

操作Index的实现算法

//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0 int Index(String S, String T, int pos) { int n,m,i; String sub; if (pos > 0) { n = StrLength(S); m = StrLength(T); i = pos; while (i <= n-m+1) { SubString(sub, S, i, m); if (StrCompare(sub, T) != 0) ++i; else return i; } } return 0; }

5.5 串的存储结构

分为顺序存储结构和链表存储结构。

5.5.1 串的顺序存储结构

一般用定长数组来定义。 一般可以将实际的串长度值保存在数组的0下标位置。有问题的，于是，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做“堆”，可由C语言的动态分配函数malloc（）和free（）来管理。

5.5.2 串的链式存储结构

与线性表相似，但由于串结构的特性，结构中每个元素都是一个字符。如果也简单的应用链表存储串值，一个节点对应一个字符，就会存在很大的空间浪费。因此，一个节点可以存放一个字符，也可考虑存放多个字符，最后一个节点若是未被占满时，可以用“#”后其他非串值字符补全。 　　但串的链式存储结构除了在连接串与串操作是有一定方便之处，总的来说，不如顺序存储灵活，性能也不如顺序存储结构好。

5.6 朴素的模式匹配算法

子串的定位操作通常称做串的模式匹配。 现在考虑不用串的其他操作，而是只用基本的数组来时实现同样的算法。注意我们假设主串S和要匹配的子串T的长度存在S[0]与T[0]中。

//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0 //T非空，1<=pos<=StrLength(S) int Index(string S, string T, int pos) { int i = pos; //i用于主串S中当前位置下标，若pos不为1，则从pos位置开始匹配 int j = 1; //j用于子串T中当前位置下标值 while (i <= S[0] && j <=T[0]) { if (S[i] == T[j]) //两字母相等则继续 { ++i; ++j; } else { // 指针后退重新开始匹配 i = i-j+2; //i退回到上次匹配首位的下一位 j = 1; //j退回到子串T的首位 } } if (j > T[0]) return i-T[0]; else retrun 0; }

平均时间复杂度为O（n+m）。最坏时间复杂度为O((n-m+1)*m)。算法太低效了。n为主串长度，m为子串长度。

5.7 KMP模式匹配算法

5.7.1 KMP模式匹配算法原理

主串S，子串T，主串的i值不回溯，也就是不可以变小，变化的是j值。j值取决于T串的结构中是否有重复的问题。 把T串各个位置的j值的变化定义为一个数组next，那么next的长度就是T串的长度。得到：

next[j]=⎧⎩⎨⎪⎪0,Maxk|1<k<j,且′p1...p′k−1=′pj−k+1...pj−1,1,当j=1时当此集合不空时其他情况

5.7.2next数组值推导

5.7.3 KMP模式匹配算法实现

// 通过计算返回子串T的next数组 void get_next(string T, int *next) { int i, j; i = 1; j = 0; next[1] = 0; while (i < T[0]) { if (j == 0 || T[i[i] == T[j]) //T[i]表示后缀的单个字符；T[j]表示前缀的单个字符 { ++i; ++j; next[i] = j; } else j = next[j]; //若字符不相同，则j值回溯 } } int Index(string S, string T, int pos) { int i= pos; //i用于主串S当前位置下标值，若pos不为1，则从pos位置开始 int j = 1; //j用于子串T中当前位置下标值 int next[255]; get_next(T,next); while (i <= S[0] && j <= T[0]) { if (j == 0 || S[i] == T[j]) // 两字母相等则继续，相对于朴素算法增加了j=0的判断 { ++i; ++j; } else{ j = next[j]; //j退回合适的位置，i值不变 } } if (j > T[0]) return i-T[0]; else return 0; }

整个算法的时间复杂度为O(n+m)。 强调：KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势，否则两者差异并不明显。

5.7.4 KMP模式匹配算法改进

//KMP算法改良 //求模式串T的next函数修正值并存入数组nextval。 void get_nextval(string T, int *nextval) { int i,j; i = 1; j = 0; nextval[1] = 0; while (i < T[0]) { if (j == 0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) //若当前字符与前缀字符不同，则当前的 j 为nextval在i位置的值 nextval[i] = j; else //如果与前缀字符相同，则将前缀字符的 nextval值赋给nextval在i位置的值 nextval[i] = nextval[j] } else j = nextval[j]; //若字符不同，则j值回溯 } }

实际匹配算法，只需要将get_next改为get_nextval。

5.7.5 nextval数组值推导

总结改进过的KMP算法，它是在计算出next值的同时，如果a位字符与它的next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next 值。

5.8 总结回顾

5.9 结尾语