第3章〓字符串 串(字符串)是一种特殊的线性表,它的数据元素仅由一个字符组成。串是计算机在处理非数值对象时常见的一种数据类型。考虑到串自身所具有的一些特性,以及串在各类算法设计实践及程序设计竞赛中的广泛应用,本章在简要介绍串的基本概念、存储结构及基本运算的基础上,重点介绍串的模式匹配算法。随着人工智能技术的不断发展和突破，模式匹配算法作为人工智能的重要组成部分，在数据挖掘、计算机视觉、自然语言处理等领域发挥着巨大的作用，以此来解决实际问题，提高生产效率以及解决人类面临的共性问题。 观看视频 3.1串类型定义 串(String)是由零个或多个任意字符组成的有限序列。一般记作s"s1s2…sn",其中s是串名; 双引号为串的定界符,双引号内的内容(s1s2…sn)为串值,引号本身不是串的内容; si(1≤i≤n)是串的元素; n为串的长度,表示串中所包含的字符个数,当n0时,称为空串,通常记为Ф。 串中任意多个连续的字符组成的子序列称为该串的子串,Ф为特殊的子串。包含子串的串称为主串。子串的第一个字符在主串中的序号称为子串的位置。当且仅当两个串的长度相等且对应字符都相同时,称为两个串相等。 ADT String{ 数据对象： D={ai | ai∈ElemSet,i=1,2,3,…,n,n≥0} 数据关系： R={ai-1, ai| ai-1, ai∈D, i=1,2,3,…,n} 基本操作集如下。 (1) StrLength(s)： 求出串s的长度。 (2) StrAssign(s1,s2)： 将s2的串值赋值给s1。 (3) StrConcat(s1,s2,s)： s1与s2连接以后的结果存于s中,原s1、s2的值不变。或StrConcat(s1,s2)： 将s2的内容连接于s1之后,s1改变,s2不变。 (4) SubStr(s,i,len)： 返回从串s的第i个字符开始的长度为len的子串。len=0或iStrLength(s)得到的是Ф,i≤StrLength(s)且lenStrLength(s)则取第i个字符开始到串的最后一个字符的子序列作为返回值。 (5) StrCmp(s1,s2)： 比较两个串s1、s2,若s1=s2,返回值0; 若s1s2,返回值0; 若s1s2,返回值0。 (6) StrIndex(s,t)： 找子串t在主串s中首次出现的位置。若t∈s,则操作返回t在s中首次出现的位置,否则返回值为-1。 (7) StrInsert(s,i,t)： 将串t插入串s的第i个字符位置上,1≤i≤StrLength(s)+1。 (8) StrDelete(s,i,len)： 删除串s中从第i个字符开始的长度为len的子串,1≤i≤StrLength(s),0≤len≤StrLength(s)-i+1。 (9) StrRep(s,t,r)： 用子串r替换串s中出现的所有子串t。 }ADT String 以上是串的几个基本操作。其中前５个操作是最为基本的,它们不能用其他操作来合成,因此通常将这５个基本操作称为最小操作集。 观看视频 3.2串的表示和实现 3.2.1串的定长顺序存储结构及其基本运算实现 1. 串的定长顺序存储结构 按预定义的大小,用一组地址连续的存储单元为每个串变量分配一个固定长度的存储区以存储串值中的字符序列。例如： #define MAXSIZE256 chars［MAXSIZE］; 则串的最大长度不能超过256个字符。 定长顺序表示带来的一个问题是如何掌握串的实际长度。以下是3种常用标识方法。 (1) 用一个指针来指向最后一个字符,其串描述如下。 typedef struct {chardata［MAXSIZE］; int curlen; } SeqString; 定义一个串变量： SeqString s; 这种存储方式可以直接得到串的长度s.curlen1，如图3.1所示。 图3.1串的顺序存储方式1 (2) 在串尾存储一个不会在串中出现的特殊字符作为串的终结符,以此表示串的结尾。例如,C语言中处理定长串的方法就是用“＼0”来表示串的结束。这种存储方法不能直接得到串的长度,而是用判断当前字符是否是“＼0”来确定串是否结束,从而可求得串的长度，如图3.2所示。 图3.2串的顺序存储方式2 (3) 设定长串存储空间char s［MAXSIZE1］，用s［0］存放串的实际长度,串值存放在s［1］~s［MAXSIZE］,字符的序号和存储位置一致,应用更为方便，如图3.3所示。 图3.3串的顺序存储方式3 2. 定长顺序串的基本运算 下面简要介绍定长顺序串连接、求子串、串比较算法,其插入和删除等运算基本与顺序表相同,在此不再赘述。 1) 串连接 把两个串s1和s2首尾连接成一个新串s,即s≤s1s2。 int StrConcat1(s1,s2,s) char s1［］,s2［］,s［］; {int i=0, j, len1, len2; len1=StrLength(s1); len2=StrLength(s2) if(len1+ len2>MAXSIZE-1)return0; /*s长度不够*/ j=0; while(s1［j］!='＼0'){ s［i］=s1［j］;i++; j++; }/*复制s1的内容到s*/ j=0; while(s2［j］!='＼0'){ s［i］=s2［j］;i++; j++; }/*复制s2的内容到s*/ s［i］='＼0'; /*在s串中建立结束标志*/ return 1; } 2) 求子串 int StrSub(char *t, char *s, int i, int len) /*用t返回串s中第i个字符开始的长度为len 的子串1≤i≤串长*/ {int slen; slen=StrLength(s); if (i<1 || i>slen || len<=0)/*i位置值不正确或len≤0时返回空串或不操作*/ return 0; for (j=0; jSMAX)returnerror;/*检查store的空间是否够,不够给出出错信息*/ else { for(i=0; ilength=s2.length;/*s1的长度定义为s2的长度*/ s1->stradr=free;/*设置s1的首地址*/ free=free+s2.length; /*修改free指针*/ } } 3) 求子串 voidStrSub(Hstring *t, Hstring s,int i,int len) /*该运算将串s中第i个字符开始的长度为len 的子串送入一个新串t中*/ {int i; if (i<0 || len<0 || len>s.len-i+1)returnerror;/*位置、长度等参数有误,给出出错信息*/ else { t->length=len; /*定义t的长度*/ t->stradr=s.stradr+i-1; /*定义t的起始地址*/ } } /*该算法本质上只是建立了一个新的串t的索引*/ 4) 串连接 void Concat(s1,s2,s) HString s1,s2; HString *s; {HString t; StrCopy(s,s1);/*将s1的内容复制到s*/ StrCopy(&t,s2);/*在前面s1内容复制之后将s2的内容复制到s*/ s->length=s1.length+s2.length; /*计算s的长度*/ } 以上扼要介绍了堆存储结构的处理思想,但诸如废弃串的回归、自由区的管理等很多问题及细节均未涉及。事实上,在常用的高级语言及开发环境中都提供了串的类型及大量的库函数,读者可直接使用,从而使算法的设计和调试更简便、可靠。 观看视频 3.2.3串的链式存储结构及其基本运算实现 1. 串的链式存储结构 串的链式存储结构即用带头结点的单链表形式存储串,称为链式串,其结点的类型定义如下。 Typedef struct node ｛Char data;　　//存放字符 Struct node *next;　　//指针域 ｝Linkstring; 针对上述串的链式存储结构,可以有非压缩存储形式和压缩存储形式两种解决方案,如图3.8(a)和图3.8(b)所示。 图3.8串的链式存储结构 (1) 非压缩存储形式: 一个结点只存储一个字符,其优点是操作方便,但存储空间利用率低。 (2) 压缩存储形式： 一个结点存储多个字符。这种存储结构提高了存储空间的利用率,但也增加了实现基本操作算法的复杂性。例如，改变串长的操作可能会涉及结点的增加与删除问题。 2. 链式串基本运算算法实现 1) 串赋值运算算法 将一个C/C++字符数组t赋给串s。 Void StrAssign(LinkString *&s, char t［］) {int i=0; LinkString *q, *tc; s=(Linkstring *) malloc(sizeof(LinkString));/*建立头结点*/ s->next=NULL;/*初始化链表指针*/ tc=s; while (t［i］!='＼0')/*将整个串逐个字符地申请结点并建立链表及相应的值*/ {q=(LinkString *) malloc(sizeof(LinkString)); q->data=t［i］; tc->next=q; tc=q; i++; } tc->next=NULL;　　/*终端结点的next置NULL*/ } 2) 串连接运算算法 将串t连接到串s之后,返回其结果。 LinkString *Concat(LinkString *s, LinkString *t) {LinkString *p=s->next, *q, *tc, *r; r=(LinkString *) malloc(sizeof(LinkString));　　//建立头结点 r->next=NULL; tc=r;　　//tc总是指向新链表的最后一个结点 while (p!=NULL)　　//将s串复制给r ｛q=(LinkString *) malloc(sizeof(LinkString)); q->data=p->data; tc->next=q; tc=q; p=p->next; ｝ p=t->next; while (p!=NULL)　　//将t串复制给r {q=(LinkString *) malloc(sizeof(LinkString)); q->data=p->data; tc->next=q; tc=q;p=p->next; } tc->next=NULL; return(r); } 3) 求子串运算算法 返回串的第i个位置开始的j个字符组成的串。 LinkString *SubStr(LinkString *s, int i, int j) {int k=1; LinkString *p=s->next, *q, *tc, *r; r=(LinkString *) malloc(sizeof(LinkString));//建立头结点 r->next=NULL; tc=r;　　//tc总是指向新链表的最后一个结点 while (knext; k++; } if (p!=NULL) {k=1; while (k<=j && p!=NULL)　　//复制j个结点 ｛q=(LinkString *) malloc(sizeof(LinkString)); q->data=p->data; tc->next=q; tc=q; p=p->next; k++; ｝ tc->next=NULL; } return (r); } 3.3串的模式匹配算法 串的模式匹配，即子串定位，是一种十分重要的串运算,也是ACM/ICPC中的高频考点。设主串s和子串t是给定的两个串,则在s中寻找t的过程称为模式匹配(Pattern Matching),且称t为模式(Pattern)。如果在s中找到等于t的子串,则称匹配成功,函数返回t在s中的首次出现的存储位置(或序号),否则匹配失败,返回1。为了运算方便,设字符串的长度存放在0号单元,串值从1号单元存放,这样字符序号与存储位置一致。 观看视频 3.3.1朴素匹配算法 朴素匹配算法思想如下： 首先将s1与t1进行比较,若不同,就将s2与t1进行比较……直到s的某一个字符si和t1相同,再将它们之后的字符进行比较,若也相同,则继续往下比较,当s的某一个字符si与t的字符tj不同时,则s返回到本趟开始字符的下一个字符,即sij2,t返回到t1,继续开始下一趟的比较,重复上述过程。若t中的字符全部比完毕,则说明本趟匹配成功,本趟的起始位置是ij1或it［0］； 否则,匹配失败。 设主串s"ababcabcacbab",模式t"abcac",匹配过程如图3.9所示。 图3.9简单模式匹配的匹配过程 依据这个思想,算法描述如下。 intStrIndex_BF(char *s,char *t) /*从串s的第一个字符开始找首次与串t相等的子串*/ {int i=1,j=1; while (i<=s［0］ && j<=t［0］)/*都没遇到结束符*/ if (s［i］==t［j］) { i++;j++; }　　/*继续*/ else {i=i-j+2; j=1;} /*回溯*/ if (j>t［0］)return (i-t［0］);　/*返回存储位置*/ elsereturn -1;/*匹配失败*/ } 该算法简称为BF算法。下面分析它的时间复杂度,设串s的长度为n,串t的长度为m。匹配成功的情况下,考虑下面两种极端情况。 (1) 在最好情况下,每趟不成功的匹配都发生在第一对字符比较时。 例如，s"aaaaaaaaaabc",t"bc"。 设匹配成功发生在si处,则字符比较次数在前面i1趟匹配中共比较了i1次,第i趟成功的匹配共比较了m次,所以共比较了i1m次。所有匹配成功的可能共有nm1种,设从si开始与t串匹配成功的概率为pi,在等概率情况下pi1/(nm1),因此最好情况下平均比较的次数是 ∑nm1i1pi×(i1m)∑nm1i11nm1×(i1m) nm2 即最好情况下的时间复杂度是O(nm)。 (2) 在最坏情况下,每趟不成功的匹配都发生在t的最后一个字符。 例如，s"aaaaaaaaaaab",t"aaab"。 设匹配成功发生在si处,则在前面i1趟匹配中共比较了(i1)×m次,第i趟成功的匹配共比较了m次,所以共比较了i×m次,因此最坏情况下平均比较的次数是 ∑nm1i1pi×(i×m)∑nm1i11nm1×(i×m) m×(nm2)2 即最坏情况下的时间复杂度是O(n*m)。 上述算法中匹配是从s串的第一个字符开始的,有时算法要求从指定位置开始,这时算法的参数表中要加一个位置参数pos： StrIndex(char *s,int pos,char *t),比较的初始位置定位在pos处,BF算法是pos1的情况。 观看视频 3.3.2KMP算法 BF算法简单但效率较低,一种对BF算法进行了很大改进的模式匹配算法是克努特(Knuth)、莫里斯(Morris)和普拉特(Pratt)同时发现的,简称KMP算法。KMP算法的关键是利用匹配失败后的信息，从失败中提取有效信息，尽量减少模式串与主串的匹配次数，省去中间所有没有意义的匹配过程，从而达到快速匹配的目的。 1. KMP算法的思想 造成BF算法速度慢的原因是回溯,即在某趟的匹配过程失败后,对于s串要回到 本趟开始字符的下一个字符,t串要回到第一个字符,而这些回溯并不是必需的。例如图3.9所示的匹配过程,在第三趟匹配过程中,s3~ s6和t1~ t4是匹配成功的,s7t5匹配失败,因此有了第四趟,其实这一趟是不必要的。由图可看出,因为在第三趟中有s4t2,而t1t2,肯定有t1s4。同理，第五趟也是没有必要的,所以从第三趟之后可以直接到第六趟,进一步分析第六趟中的第一对字符s6和t1的比较也是多余的,因为第三趟中已经比过了s6和t4,并且s6t4,而t1t4,必有s6t1,因此第六趟的比较可以从第二对字符s7和t2开始进行。这就是说,第三趟匹配失败后,指针i不动,而是将模式串t向右“滑动”,用t2 “对准” s7继续进行,以此类推。这样的处理方法指针i是无回溯的。 综上所述,希望某趟在si和tj匹配失败后,指针i不回溯,模式串t向右“滑动”至某个位置上,使得tk对准si继续向右进行。显然,现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k,即si和tj匹配失败后,指针i不动,模式串t向右“滑动”,使tk和si对准继续向右进行比较,要满足这一假设,就要有如下关系成立： "t1 t2 …tk1""sik1 sik2 …si1" (3.1) 式(3.1)左边是tk前面的k1个字符,右边是si前面的k1个字符。 而本趟匹配失败是在si和tj之处,已经得到的部分匹配结果是 "t1 t2 …tj1""sij1 sij2 …si1" (3.2) 因为kj,所以有 "tjk1 tjk2 …tj1""sik1 sik2 …si1" (3.3) 式(3.3)左边是tj前面的k1个字符,右边是si前面的k1个字符, 通过式(3.1)和式(3.3)得到关系： "t1 t2 …tk1""tjk1 tjk2 …tj1" (3.4) 结论： 某趟在si和tj匹配失败后,如果模式串中有满足关系（见式(3.4)）的子串存在,即模式串中的前k1个字符与模式串中tj字符前面的k1个字符相等时,模式串t就可以向右“滑动”致使tk和si对准,继续向右进行比较即可。 观看视频 2. next函数 模式串中的每一个tj都对应一个k值,由式(3.4)可知,这个k值仅依赖于模式串t本身字符序列的构成,而与主串s无关。用next［j］表示tj对应的k值,根据以上分析,next函数有如下性质。 (1) next［j］是一个整数,且0≤next［j］j。 (2) 为了使t的右移不丢失任何匹配成功的可能,当存在多个满足式(3.4)的k值时,应取最大的,这样向右“滑动”的距离最短,“滑动”的字符为jnext［j］个。 (3) 如果在tj前不存在满足式(3.4)的子串,此时若t1tj,则k1;若t1tj,则k0。这时“滑动”的最远,为j1个字符，即用t1和sj1继续比较。 因此,next函数定义如下： next［j］ 0，j1 k{k|1≤k＜j且"t1 t2 …tk1" "tjk1 tjk2…tj1"} 1不存在上面的k且t1tj 0不存在上面的k且t1tj 设有模式串t"abcaababc",则它的next函数值为 j123456789 模式串abcaababc next［j］011021311 观看视频 3. KMP算法 在求得模式的next函数之后,匹配可按如下方法进行： 假设以指针i和j分别指示主串和模式中的比较字符,令i的初值为pos,j的初值为1。若在匹配过程中sitj（j=1）,则i和j分别增１； 若sitj（j≠1）匹配失败,则i不变,j退到next［j］位置再比较,若相等,则指针各自增１,否则j再退到下一个next值的位置,以此类推。直至下列两种情况： 一种是j退到某个next值时字符比较相等,则i和j分别增１，并继续进行匹配;另一种是j退到值为零(即模式的第一个字符失配),则此时i和j也要分别增１,表明从主串的下一个字符起和模式重新开始匹配。 设主串s"aabcbabcaabcaababc",子串t"abcaababc",图3.10是一个利用next函数进行匹配的过程示意图。 图3.10利用模式next函数进行匹配的过程示例 在假设已有next函数情况下,KMP算法如下。 int StrIndex_KMP(char *s,char *t,int pos) /*从串s的第pos个字符开始找首次与串t相等的子串*/ {int i=pos,j=1,slen,tlen; while (i<=s［0］ && j<=t［0］) /*都没遇到结束符*/ if (j==0||s［i］==t［j］) { i++; j++; } elsej=next［j］; /*回溯*/ if (j>t［0］)returni-t［0］;　/*匹配成功,返回存储位置*/ elsereturn-1; } 4. 如何求next函数 由以上讨论可知,next函数值仅取决于模式本身而和主串无关。可以从分析next函数的定义出发用递推的方法求得next函数值。 由定义知： next［1］0 (3.5) 设next［j］k,即有 "t1 t2 …tk1""tjk1 tjk2 …tj1" (3.6) next［j1］可能有以下两种情况。 第一种情况： 若tk tj,则表明在模式串中 "t1 t2 …tk""tjk1 tjk2 …tj" (3.7) 这就是说next［j1］k1,即 next［j１］next［j］1 (3.8) 第二种情况： 若tk tj,则表明在模式串中 "t1 t2 …tk""tjk1 tjk2 …tj" (3.9) 此时可把求next函数值的问题看成一个模式匹配问题,整个模式串既是主串又是模式,而当前在匹配的过程中,已有式(3.6)成立,则当tk tj时应将模式向右滑动,使得第next［k］个字符和“主串”中的第j个字符相比较。若next［k］k′,且tk′tj,则说明在主串中第j1个字符之前存在一个最大长度为k′的子串,使得 "t1 t2 …tk′""tjk′1 tj k′2 …tj" (3.10) 因此 next［j1］next［k］1 (3.11) 同理，若tk′tj,则将模式继续向右滑动致使第next［k′］个字符和tj对齐,以此类推,直至tj和模式中的某个字符匹配成功或者不存在任何k′(1 k′k …j)满足式(3.10),此时若t1tj1,则有 next［j1］1 (3.12) 否则若t1tj1,则有 next［j1］0 (3.13) 综上所述,求next函数值过程的算法如下。 void GetNext(char *t,int next［ ］) /*求模式t的next值并存入next数组中*/ ｛int i=1,j=0; next［1］=0; while (i0&&t［i］!=t［j］)j=next［j］; i++;j++; if (t［i］==t［j］)next［i］=next［j］; elsenext［i］=j; } } 上述算法的时间复杂度是O(m)，所以KMP算法的时间复杂度是O(n×m),但在一般情况下,实际的执行时间是O(nm)。当然，KMP算法和简单的模式匹配算法相比,设计难度增加很大,我们主要学习该算法的设计技巧。 3.3.3基于KMP算法的应用举例 下面给出的是一个ACM/ICPC的实战练习题Oulipo,题目请见POJ网。［POJ 3461］ 题目要求： 给出两个字符串,求出模式串pat在主串text中出现了多少次。 输入 The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:  One line with the word W, a string over {'A', 'B', 'C', …, 'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W).  One line with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤ 1,000,000. 输出 For every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T. 输入示例输出示例 31 BAPC3 BAPC0 AZA AZAZAZA VERDI AVERDXIVYERDIAN 参考程序如下： #include #include #include using namespace std; const int nMax=10005; const int mMax=1000005; char text［mMax］,pat［nMax］; int lent,lenp,next［nMax］; void get_next(){/*计算模式串的next函数*/ int i,j=-1; next［0］=-1; for(i=1;i<=lenp;i++){ //pat［j］可以理解为i的前一个字符的next值所指向的字符 while (j>-1&&pat［j+1］!=pat［i］) j=next［j］; if(pat［j+1］==pat［i］) j++; next［i］=j; } } int KMP(){ int ans=0,i=0,j=-1; get_next(); /*调用next函数查找匹配情况*/ for(i=0;i