《【精品】【考研计算机专业课】武汉大学数据结构ppt课件 第4章串（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】武汉大学数据结构ppt课件 第4章串（可编辑.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【考研计算机专业课】武汉大学数据结构PPT课件 第4章 串 串串(或或字字符符串串),是是由由零零个个或或多多个个字字符符组组成成的的有有穷穷序序列列。含含零个字符的串称为空串零个字符的串称为空串,用用表示。表示。串中所含字符的个数称为该串的串中所含字符的个数称为该串的长度长度(或串长或串长)。通通常常将将一一个个串串表表示示成成a1a2an的的形形式式。其其中中,最最外外边边的的双双引引号号本本身身不不是是串串的的内内容容,它它们们是是串串的的标标志志,以以便便将将串串与与标标识识符符(如变量名等如变量名等)加以区别。每个加以区别。每个ai(1in)代表一个字符。代表一个字符。4.1 4.1
2、 串的基本概念串的基本概念 当当且且仅仅当当两两个个串串的的长长度度相相等等并并且且各各个个对对应应位位置置上上的的字字符符都都相同时相同时,这两个串才是相等的。这两个串才是相等的。一一个个串串中中任任意意个个连连续续字字符符组组成成的的子子序序列列(含含空空串串,但但不不含含串串本本身身)称称为为该该串串的的子子串串。例例如如,“a”、“ab”、“abc”和和“abcd”等等都都是是“abcde”的的子串子串（真子串真子串是指不包含自身的所有子串）。是指不包含自身的所有子串）。思考题：思考题：串和线性表串和线性表有什么异同？有什么异同？例例4.1 问题问题:“abcde”有多少个真子串有多少
3、个真子串?解解:空串数空串数:1含含1个字符的子串数个字符的子串数:5含含2个字符的子串数个字符的子串数:4含含3个字符的子串数个字符的子串数:3含含4个字符的子串数个字符的子串数:2共有共有1+2+3+4+5=15个子串。个子串。（8）DelStr(s,i,j):从从串串s中中删删去去从从第第i(1iStrLength(s)个个字字符开始的长度为符开始的长度为j的子串的子串,并返回产生的新串。并返回产生的新串。（9）RepStr(s,i,j,t):替替换换:在在串串s中中,将将第第i(1iStrLength(s)个个字符开始的字符开始的j个字符构成的子串用串个字符构成的子串用串t替换替换,并
4、返回产生的新串。并返回产生的新串。（10）DispStr(s):串输出串输出:输出串输出串s的所有元素值。的所有元素值。4.2.1 4.2.1 串的顺序存储及其基本操作实现串的顺序存储及其基本操作实现 串串是是一一种种特特殊殊的的线线性性表表,在在非非紧紧缩缩格格式式中中,它它的的每每个个结结点点仅仅由由一一个个字字符符组组成成,因因此此存存储储串串的的方方法法也也就就是是存存储储线线性性表表的的一一般般方方法法。存存储储串串最最常常用用的的方方式式是是采采用用顺顺序序存存储储,即即把把串串的的字字符符顺顺序序地地存存储储在内存一片相邻的空间在内存一片相邻的空间,这称为这称为顺序串顺序串。4.
5、2 4.2 串的存储结构串的存储结构 顺序存储采用一般顺序表的存储结构顺序存储采用一般顺序表的存储结构,其类型定义如下其类型定义如下:#define MaxSize 100 typedef struct char dataMaxSize;int length;SqString;其其中中,data域域用用来来存存储储字字符符串串,length域域用用来来存存储储字字符符串串的的当当前前长长度度,MaxSize常常量量表表示示允允许许所所存存储储字字符符串串的的最最大大长长度度。在在C语语言中每个字符串以言中每个字符串以0标志结束。标志结束。顺序串中实现串的基本运算如下顺序串中实现串的基本运算如下
6、:（1）StrAssign(str,cstr)将一个字符串常量赋给串将一个字符串常量赋给串str,即生成一个其值等于即生成一个其值等于cstr的串的串s。void StrAssign(SqString&str,char cstr)int i;for(i=0;cstri!=0;i+)str.datai=cstri;str.length=i;（2）StrCopy(s,t)将串将串t复制给串复制给串s。void StrCopy(SqString&s,SqString t)/引用型参数引用型参数 int i;for(i=0;it.length;i+)s.datai=t.datai;s.length=t
7、.length;（3）StrEqual(s,t)判判断断两两个个串串是是否否相相等等:若若两两个个串串s与与t相相等等返返回回真真(1)；否否则则返返回回假假(0)。int StrEqual(SqString s,SqString t)int same=1,i;if(s.length!=t.length)same=0;/长度不相等时返回长度不相等时返回0 else for(i=0;is.length;i+)if(s.datai!=t.datai)/有一个对应字符不同时返回有一个对应字符不同时返回0 same=0;break;return same;（4）StrLength(s)求串长求串长:返
8、回串返回串s中字符个数。中字符个数。int StrLength(SqString s)return s.length;（5）Concat(s,t)返回由两个串返回由两个串s和和t连接在一起形成的新串。连接在一起形成的新串。SqString Concat(SqString s,SqString t)SqString str;int i;str.length=s.length+t.length;for(i=0;is.length;i+)str.datai=s.datai;for(i=0;it.length;i+)str.datas.length+i=t.datai;return str;（6）Su
9、bStr(s,i,j)返返回回串串s中中从从第第i(1iStrLength(s)个个字字符符开开始始的的、由由连连续续j个个字符组成的子串。字符组成的子串。SqString SubStr(SqString s,int i,int j)SqString str;int k;str.length=0;if(is.length|js.length)printf(参数不正确参数不正确n);return str;/参数不正确时返回空串参数不正确时返回空串 for(k=i-1;ki+j-1;k+)str.datak-i+1=s.datak;str.length=j;return str;（7）InsStr
10、(s1,i,s2)将将串串s2插插入入到到串串s1的的第第i个个字字符符中中,即即将将s2的的第第一一个个字字符符作作为为s1的第的第i个字符个字符,并返回产生的新串。并返回产生的新串。SqString InsStr(SqString s1,int i,SqString s2)int j;SqString str;str.length=0;if(is1.length+1)printf(参数不正确参数不正确n);return s1;for(j=0;ji-1;j+)str.dataj=s1.dataj;for(j=0;js2.length;j+)str.datai+j-1=s2.dataj;for
11、(j=i-1;js1.length;j+)str.datas2.length+j=s1.dataj;str.length=s1.length+s2.length;return str;（8）DelStr(s,i,j)从从串串s中中删删去去第第i(1iStrLength(s)个个字字符符开开始始的的长长度度为为j的的子子串串,并返回产生的新串。并返回产生的新串。SqString DelStr(SqString s,int i,int j)int k;SqString str;str.length=0;if(is.length|i+js.length+1)/参数不正确时返回空串参数不正确时返回空串
12、 printf(参数不正确参数不正确n);return str;for(k=0;ki-1;k+)str.datak=s.datak;for(k=i+j-1;ks.length;k+)str.datak-j=s.datak;str.length=s.length-j;return str;（9）RepStr(s,i,j,t)在在串串s中中,将将第第i(1iStrLength(s)个个字字符符开开始始的的j个个字字符符构构成成的的子子串用串串用串t替换替换,并返回产生的新串。并返回产生的新串。SqString RepStr(SqString s,int i,int j,SqString t)int
13、 k;SqString str;str.length=0;if(is.length|i+j-1s.length)/参数不正确时返回空串参数不正确时返回空串 printf(参数不正确参数不正确n);return str;for(k=0;ki-1;k+)str.datak=s.datak;for(k=0;kt.length;k+)str.datai+k-1=t.datak;for(k=i+j-1;k0)for(i=0;it的字符的字符,返回返回1；若若s的字符的字符t的字符的字符,返回返回-1；若若s的字符的字符=t的字符的字符,按上述规则继续比较。按上述规则继续比较。(2)当当(1)中对应字符均
14、相同时中对应字符均相同时,比较比较s1和和s2的长度的长度:两者相等时两者相等时,返回返回0；s的长度的长度t的长度的长度,返回返回1；s的长度的长度t的长度的长度,返回返回-1。int Strcmp(SqString s,SqString t)int i,comlen;if(s.lengtht.length)comlen=s.length;else comlen=t.length;/求求s s和和t t的共同长度的共同长度 for(i=0;icomlen;i+)/逐个字符比较逐个字符比较 if(s.datait.datai)return 1;if(s.length=t.length)/s=t
15、 return 0;else if(s.lengtht.length)/st4.2.2 4.2.2 串的链式存储及其基本操作实现串的链式存储及其基本操作实现 也也可可以以采采用用链链式式方方式式存存储储串串,即即用用单单链链表表形形式式存存储储串串。这这称为称为链式串链式串或或链串链串。链串中的结点类型定义链串中的结点类型定义:typedef struct snode char data;struct snode*next;LiString;其其中中data域域用用来来存存储储组组成成字字符符串串的的字字符符，next域域用用来来指指向向下下一一个个结结点点。每每个个字字符符对对应应一一个个结
16、结点点，一一个个这这样样的的链链表表存存储一个字符串。下图所示是一个结点大小为储一个字符串。下图所示是一个结点大小为1的链串。的链串。链串示意图链串示意图 下面讨论在链串上实现串基本运算的算法。下面讨论在链串上实现串基本运算的算法。（1）StrAssign(s,t)将将一一个个字字符符串串常常量量t赋赋给给串串s,即即生生成成一一个个其其值值等等于于t的的串串s。以以下采用尾插法建立链串。下采用尾插法建立链串。void StrAssign(LiString*&s,char t)int i;LiString*r,*p;/r始终指向尾结点始终指向尾结点 s=(LiString*)malloc(si
17、zeof(LiString);r=s;for(i=0;ti!=0;i+)p=(LiString*)malloc(sizeof(LiString);p-data=ti;r-next=p;r=p;r-next=NULL;（2）StrCopy(s,t)将串将串t复制给串复制给串s。以下采用尾插法建立复制后的链串。以下采用尾插法建立复制后的链串s。void StrCopy(LiString*&s,LiString*t)LiString*p=t-next,*q,*r;s=(LiString*)malloc(sizeof(LiString);r=s;/r始终指向尾结点始终指向尾结点 while(p!=NU
18、LL)/将将t的所有结点复制到的所有结点复制到s q=(LiString*)malloc(sizeof(LiString);q-data=p-data;r-next=q;r=q;p=p-next;r-next=NULL;（3）StrEqual(s,t)判判断断两两个个串串是是否否相相等等:若若两两个个串串s与与t相相等等则则返返回回真真(1)；否否则则返返回假回假(0)。int StrEqual(LiString*s,LiString*t)LiString*p=s-next,*q=t-next;while(p!=NULL&q!=NULL&p-data=q-data)p=p-next;q=q-n
19、ext;if(p=NULL&q=NULL)return 1;else return 0;（4）StrLength(s)求串长求串长:返回串返回串s中字符个数。中字符个数。int StrLength(LiString*s)int i=0;LiString*p=s-next;while(p!=NULL)i+;p=p-next;return i;（5）Concat(s,t)返回由两个串返回由两个串s和和t连接在一起形成的新串。连接在一起形成的新串。LiString*Concat(LiString*s,LiString*t)LiString*str,*p=s-next,*q,*r;str=(LiStr
20、ing*)malloc(sizeof(LiString);r=str;while(p!=NULL)/将将s的所有结点复制到的所有结点复制到str q=(LiString*)malloc(sizeof(LiString);q-data=p-data;r-next=q;r=q;p=p-next;p=t-next;while(p!=NULL)/将将t的所有结点复制到的所有结点复制到str q=(LiString*)malloc(sizeof(LiString);q-data=p-data;r-next=q;r=q;p=p-next;r-next=NULL;return str;（6）SubStr(s
21、,i,j)返返回回串串s中中从从第第i(1iStrLength(s)个个字字符符开开始始的的、由由连连续续j个个字字符组成的子串。符组成的子串。LiString*SubStr(LiString*s,int i,int j)int k;LiString*str,*p=s-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确参数不正确n);return str;/参数不正确时返回空串参数不正确时返回空串 for(k=0;knext;for(k=1;kstr
22、 q=(LiString*)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;r-next=NULL;return str;（7）InsStr(s1,i,s2)将将串串s2插插入入到到串串s1的的第第i(1iStrLength(s)+1)个个字字符符中中,即即将将s2的第一个字符作为的第一个字符作为s1的第的第i个字符个字符,并返回产生的新串。并返回产生的新串。LiString*InsStr(LiString*s,int i,LiString*t)int k;LiString*str,*p=s-nex
23、t,*p1=t-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)+1)printf(参数不正确参数不正确n);return str;/参数不正确时返回空串参数不正确时返回空串 for(k=1;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;while(p1!=NULL)/将将t的所有结点复制到的所有结点复制到str q=(LiString*)malloc(sizeof(LiString);q-data=p1-data;q-next=NULL;r-next
24、=q;r=q;p1=p1-next;while(p!=NULL)/将将*p及其后的结点复制到及其后的结点复制到str q=(LiString*)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;r-next=NULL;return str;（8）DelStr(s,i,j)从从串串s中中删删去去从从第第i(1iStrLength(s)个个字字符符开开始始的的长长度度为为j的的子子串串,并返回产生的新串。并返回产生的新串。LiString*DelStr(LiString*s,int i,int j)int
25、 k;LiString*str,*p=s-next,*q,*r;str=(LiString*)malloc(sizeof(LiString);r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确参数不正确n);return str;/参数不正确时返回空串参数不正确时返回空串 for(k=0;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;for(k=0;knext;while(p!=NULL)/将将*p及其后的结点复制到及其后的结点复制到str q=(LiString*)malloc(sizeof(LiS
26、tring);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;r-next=NULL;return str;（9）RepStr(s,i,j,t)在在串串s中中,将将第第i(1iStrLength(s)个个字字符符开开始始的的j个个字字符符构构成成的的子子串用串串用串t替换替换,并返回产生的新串。并返回产生的新串。LiString*RepStr(LiString*s,int i,int j,LiString*t)int k;LiString*str,*p=s-next,*p1=t-next,*q,*r;str=(LiString*)malloc(s
27、izeof(LiString);r=str;if(iStrLength(s)|jStrLength(s)printf(参数不正确参数不正确n);return str;/参数不正确时返回空串参数不正确时返回空串 for(k=0;kdata=p-data;q-next=NULL;r-next=q;r=q;p=p-next;for(k=0;knext;while(p1!=NULL)/将将t的所有结点复制到的所有结点复制到str q=(LiString*)malloc(sizeof(LiString);q-data=p1-data;q-next=NULL;r-next=q;r=q;p1=p1-next
28、;while(p!=NULL)/将将*p及其后的结点复制到及其后的结点复制到str q=(LiString*)malloc(sizeof(LiString);q-data=p-data;q-next=NULL;r-next=q;r=q;p=p-next;r-next=NULL;return str;（10）DispStr(s)输出串输出串s的所有元素值。的所有元素值。void DispStr(LiString*s)LiString*p=s-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);例例4.3 在在链链串串中中,设设计计一一个
29、个算算法法把把最最先先出出现现的的子子串串ab改为改为xyz。解解:在在串串s中中找找到到最最先先出出现现的的子子串串ab,p指指向向data域域值值为为a的的结结点点,其其后后为为data域域值值为为b的的结结点点。将将它它们们的的data域域值值分分别别改改为为x和和z,再再创创建建一一个个data域域值值为为y的的结结点点,将将其其插插入入到到*p之之后。本例算法如下后。本例算法如下:abxzyq修改修改ppvoid Repl(LiString*&s)LiString*p=s-next,*q;int find=0;while(p-next!=NULL&find=0)if(p-data=a
30、&p-next-data=b)p-data=x;p-next-data=z;/替换为替换为xyz q=(lstring*)malloc(sizeof(lstring);q-data=y;q-next=p-next;p-next=q;find=1;else p=p-next;4.3 串的模式匹配串的模式匹配 设有主串设有主串s和子串和子串t,子串子串t的定位就是要在主串的定位就是要在主串s中找到一中找到一个与子串个与子串t相等的子串。通常把主串相等的子串。通常把主串s称为目标串称为目标串,把子串把子串t称称为模式串为模式串,因此定位也称作因此定位也称作模式匹配模式匹配。模式匹配成功是指在目标串模
31、式匹配成功是指在目标串s中找到一个模式串中找到一个模式串t；不成；不成功则指目标串功则指目标串s中不存在模式串中不存在模式串t。4.4.1 Brute-Force算法算法 Brute-Force简称为简称为BF算法算法,亦称简单匹配算法亦称简单匹配算法,其基本思其基本思路是路是:从目标串从目标串s=s0s1sn-1的第一个字符开始和模式串的第一个字符开始和模式串t=t0t1tm-1中的第一个字符比较中的第一个字符比较,若相等若相等,则继续逐个比较后则继续逐个比较后续字符；否则从目标串续字符；否则从目标串s的第二个字符开始重新与模式串的第二个字符开始重新与模式串t的的第一个字符进行比较。依次类推
32、第一个字符进行比较。依次类推,若从模式串若从模式串s的第的第i个字符开个字符开始始,每个字符依次和目标串每个字符依次和目标串t中的对应字符相等中的对应字符相等,则匹配成功则匹配成功,该该算法返回算法返回i；否则；否则,匹配失败匹配失败,函数返回函数返回-1。s=“a b c a b c d a b c d e”t=“a b c d”例如例如,设目标串设目标串s=“abcabcdabcde”,模式串模式串t=“abcd”。BF模式匹配过程如下所示。模式匹配过程如下所示。ikjs=“a b c a b c d a b c d e”t=“a b c d”ikjs=“a b c a b c d a b
33、 c d e”t=“a b c d”iks=“a b c a b c d a b c d e”t=“a b c d”ikjjk=t.length作为找到子串的条件。作为找到子串的条件。int indexpos(SqString str,SqString substr)int i,j,k,idx=-1;for(i=0;istr.length;i+)for(j=i,k=0;str.dataj=substr.datak;j+,k+);if(k=substr.length)/注意注意j每次从每次从i开始开始,有回溯有回溯 return(i);return(-1);算法算法1 可以少一个扫描变量。可以少
34、一个扫描变量。例如例如,设目标串设目标串s=“cddcdc”,模式串模式串t=“cdc”。BF模式匹配过程如下所示。模式匹配过程如下所示。int index(SqString s,SqString t)int i=0,j=0;while(is.length&j=t.length)return(i-t.length);/返回匹配的第一个字符的下标返回匹配的第一个字符的下标 else return-1;/模式匹配不成功模式匹配不成功 算法算法2 这个算法简单这个算法简单,易于理解易于理解,但效率不高但效率不高,主要原因是主要原因是:主串指针主串指针i在若干个字符序列比较相等后在若干个字符序列比较相
35、等后,若有一个字符比较不相等若有一个字符比较不相等,仍需仍需回溯回溯（即（即i=i-j+1）。）。该算法在最好情况下的时间复杂度为该算法在最好情况下的时间复杂度为O(m),即主串的前即主串的前m个个字符正好等于模式串的字符正好等于模式串的m个字符。在最坏情况下的时间复杂度个字符。在最坏情况下的时间复杂度为为O(n*m)。4.3.2 KMP算法算法 KMP算法是算法是D.E.Knuth、J.H.Morris和和V.R.Pratt共同提共同提出的出的,简称简称KMP算法。该算法较算法。该算法较BF算法有较大改进算法有较大改进,主要是消主要是消除了主串指针的回溯除了主串指针的回溯,从而使算法效率有了
36、某种程度的提高。从而使算法效率有了某种程度的提高。Donald Knuth（1938年），算法和程序年），算法和程序设计技术的先驱者，计算机排版系统设计技术的先驱者，计算机排版系统TEX和和METAFONT的发明者，他因这些成就和的发明者，他因这些成就和大量创造性的影响深远的著作（大量创造性的影响深远的著作（19部书和部书和160篇论文）而誉满全球。作为斯坦福大学篇论文）而誉满全球。作为斯坦福大学计算机程序设计艺术的荣誉退休教授，计算机程序设计艺术的荣誉退休教授，他当他当前正全神贯注于完成其关于计算机科学的史前正全神贯注于完成其关于计算机科学的史诗性的七卷集。这一伟大工程在诗性的七卷集。这一伟
37、大工程在1962年他还年他还是加利福尼亚理工学院的研究生时就开始了是加利福尼亚理工学院的研究生时就开始了。他于他于1974年获得计算机科学界最高奖图灵年获得计算机科学界最高奖图灵奖。奖。s=abcabababcdet=ababcj01234tjababcNextj-10012t t中中”b”a”,”b”a”,而而s s中中”b”=t”b”=t中中”b”,”b”,故不必从故不必从s1s1开始开始s=abcabababcdet=ababc不相等不相等,s,s后移后移s=abcabababcdet=ababc没有必要从没有必要从s4s4开始开始s=abcabababcdet=ababc成功成功 所所
38、谓谓真真子子串串是是指指模模式式串串t存存在在某某个个k(0kj)，使使得得t0t1tk =tj-ktj-k+1tj 成立。成立。例如，例如，t=abab,即即t0t1t2t3 也就是说，也就是说，“ab”是是真子串真子串。真真子子串串就就是是模模式式串串中中隐隐藏藏的的信信息息，利利用用它它来来提提高高模模式式匹匹配配的效率。的效率。不同于前面的子真串的定义不同于前面的子真串的定义 一一般般情情况况:设设主主串串s=s0s1sn-1,模模式式t=t0t1tm-1,在在进进行行第第i趟匹配时，出现以下情况：趟匹配时，出现以下情况：这时，应有这时，应有t0t1tj-1=si-jsi-j+1si-
39、1 (4.1)如果在模式如果在模式t中，中，t0t1tj-1t1t2tj(4.2)则则回回溯溯到到si-j+1开开始始与与t匹匹配配，必必然然“失失配配”，理理由由很很简简单单：由由(4.1)式和式和(4.2)式综合可知：式综合可知：t0t1tj-1si-j+1si-j+2si 既既然然如如此此，回回溯溯到到si-j+1开开始始与与t匹匹配配可可以以不不做做。那那么么，回回溯溯到到si-j+2开始与开始与t匹配又怎么样？从上面推理可知，如果匹配又怎么样？从上面推理可知，如果:t0t1tj-2t2t3tj仍然有仍然有 t0t1tj-2si-j+2si-j+3si 这这样样的的比比较较仍仍然然“失
40、失配配”。依依此此类类推推，直直到到对对于于某某一一个个值值k，使得：使得：t0t1tk-2 tj-k+1tj-k+2tj-1 且且 t0t1tk-1=tj-ktj-k+1tj-1 才有才有 tj-ktj-k+1tj-1=si-ksi-k+1si-1=t0t1tk-1 说明下一次可直接比较说明下一次可直接比较si和和tk，这样，我们可以直接把，这样，我们可以直接把第第i趟比较趟比较“失配失配”时的模式时的模式t从当前位置直接右滑从当前位置直接右滑j-k位。而这位。而这里的里的k即为即为nextj。例例如如t=abab,由由于于t0t1=t2t3(这这里里k=1,j=3),则则存存在在真真子串。
41、设子串。设s=abacabab,t=abab,第一次匹配过程如下所示。第一次匹配过程如下所示。此时不必从此时不必从i=1(i=i-j+1=1),j=0重新开始第二次匹配。因重新开始第二次匹配。因t0t1,s1=t1,必有必有s1t0,又因又因t0=t2,s2=t2,所以必有所以必有s2=t0。因此。因此,第第二次匹配可直接从二次匹配可直接从i=3,j=1开始。开始。为此为此,定义定义nextj函数（函数（失配函数失配函数）如下）如下:maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1”当此集合非空时当此集合非空时 -1 当当j=0时时 0 其他情况其他情况nextj=j
42、0123tjababnextj-1001t=“abab”t=“abab”对应的对应的nextnext数组如下数组如下:void GetNext(SqString t,int next)int j,k;j=0;k=-1;next0=-1;while(jt.length-1)if(k=-1|t.dataj=t.datak)/k为为-1或比较的字符相等时或比较的字符相等时 j+;k+;nextj=k;else k=nextk;由由模模式式串串t求求出出next值值的的算算法法int KMPIndex(SqString s,SqString t)int nextMaxSize,i=0,j=0;GetN
43、ext(t,next);while(is.length&j=t.length)return(i-t.length);else return-1;/返回不匹配标志返回不匹配标志 KMP算法算法 设主串设主串s的长度为的长度为n,子串子串t长度为长度为m。在在KMP算算法法中中求求next数数组组的的时时间间复复杂杂度度为为O(m),在在后后面面的的匹匹配配中中因因主主串串s的的下下标标不不减减即即不不回回溯溯,比比较较次次数数可可记记为为n,所所以以KMP算法总的时间复杂度为算法总的时间复杂度为O(n+m)。例如例如,设目标串设目标串s=“aaabaaaab”,模式串模式串t=“aaaab”。s
44、的长的长度为度为n(n=9),t的长度为的长度为m(m=5)。用指针。用指针i指示目标串指示目标串s的当前的当前比较字符位置比较字符位置,用指针用指针j指示模式串指示模式串t的当前比较字符位置。的当前比较字符位置。KMP模式匹配过程如下所示。模式匹配过程如下所示。j01234tjaaaabnextj-10123 上述定义的上述定义的next在某些情况下尚有缺陷。在某些情况下尚有缺陷。例如例如,模式模式“aaaab”在和主串在和主串“aaabaaaab”匹配时：匹配时：当当i=3,j=3时时,s.data3t.data3,由由nextj的指示还需进行的指示还需进行i=3、j=2,i=3、j=1,
45、i=3、j=0等三次比较。等三次比较。实际上实际上,因为模式中的第因为模式中的第1、2、3个字符和第个字符和第4个字符都相个字符都相等等,因此因此,不需要再和主串中第不需要再和主串中第4个字符相比较个字符相比较,而可以将模式一而可以将模式一次向右滑动次向右滑动4个字符的位置直接进行个字符的位置直接进行i=4,j=0时的字符比较。时的字符比较。这就是说这就是说,若按上述定义得到若按上述定义得到nextj=k,而模式中而模式中pj=pk,则为则为主串中字符主串中字符si和和pj比较不等时比较不等时,不需要再和不需要再和pk进行比较进行比较,而直接和而直接和pnextk进行比较进行比较,换句话说换句
46、话说,此时的此时的nextj应和应和nextk相同。相同。为此将为此将nextj修正为修正为nextvalj：比较比较t.dataj和和t.datak，若不等，则，若不等，则 nextvalj=nextj;若若相等相等nextvalj=nextvalk;void GetNextval(SqString t,int nextval)int j=0,k=-1;nextval0=-1;while(jt.length)if(k=-1|t.dataj=t.datak)j+;k+;if(t.dataj!=t.datak)nextvalj=k;else nextvalj=nextvalk;else k=ne
47、xtvalk;由模式串由模式串t求求出出nextval值值int KMPIndex1(SqString s,SqString t)int nextvalMaxSize,i=0,j=0;GetNextval(t,nextval);while(is.length&j=t.length)return(i-t.length);else return-1;/返回不匹配标志返回不匹配标志 修改后的修改后的KMP算法算法j01234tjaaaabnextj-10123nextvalj-1-1-1-13思考题：思考题：KMP算法给我们什么启示？算法给我们什么启示？为为m2行行n2列列设设P为为m1行行n1列，
48、列，设设M求匹配成功的位置。要求用尽可能高效的算法。求匹配成功的位置。要求用尽可能高效的算法。DNA子序列子序列DNA序列序列上机实验题上机实验题小知识：小知识：Karp Rabin Karp Rabin 算法算法 Karp Rabin 算法是利用算法是利用hash函数的特性进行字符串匹配的。函数的特性进行字符串匹配的。KR算法对模式串和循环中每一次要匹配的子串按一定的算法对模式串和循环中每一次要匹配的子串按一定的hash函数求值，如果函数求值，如果hash值相同，才进一步比较这两个串是值相同，才进一步比较这两个串是否真正相等。否真正相等。也许你会有这样的疑问，在也许你会有这样的疑问，在Bru
49、te force暴力匹配中，每一次暴力匹配中，每一次都把模式串和文本当前字串匹配，现在每一次都计算都把模式串和文本当前字串匹配，现在每一次都计算hash，还要进一步比较，会不会更慢呢？还要进一步比较，会不会更慢呢？答案肯定是不会啦，而且事实上答案肯定是不会啦，而且事实上KR算法效率很高算法效率很高第一：不同子串第一：不同子串hash值相同是小概率事件值相同是小概率事件第二：第二：hash函数设计合理的情况下，计算速度相当快函数设计合理的情况下，计算速度相当快第三：虽然理论上第三：虽然理论上KR算法的时间复杂度是算法的时间复杂度是O(m*n),但现实应但现实应用中一般是用中一般是O(m+n)。本
50、文使用的本文使用的hash函数如下：函数如下：hash(str0.m-1)=(str0*2m-1+str1*2m-2+strm-1*20)mod qq是一个较大的数，而且最好是素数，而且是大于是一个较大的数，而且最好是素数，而且是大于m的素数。的素数。计算时，计算时，*2的运算就使用移位代替了的运算就使用移位代替了在下面的实现代码中，在下面的实现代码中，q取整形最大值，也就是说，可以不用进行取整形最大值，也就是说，可以不用进行模运算了，这种偷工减料的做法只能在模式串很短的情形下才可以模运算了，这种偷工减料的做法只能在模式串很短的情形下才可以用，要不然会溢出的。粗略算了一下，如果模式串是用，要不