《数据结构第3版第4章串》由会员分享，可在线阅读，更多相关《数据结构第3版第4章串（66页珍藏版）》请在金锄头文库上搜索。
1、第第4 4.1 串的基本概念串的基本概念4.2 串的存储结构串的存储结构 本章小结本章小结4.3 串的模式匹配串的模式匹配 串串（或或字字符符串串），是是由由零零个个或或多多个个字字符符组组成成的的有有穷穷序序列列。含零个字符的串称为空串，用含零个字符的串称为空串，用表示。表示。 串中所含字符的个数称为该串中所含字符的个数称为该串的长度串的长度（或串长）。（或串长）。 通通常常将将一一个个串串表表示示成成“a1a2an”的的形形式式。其其中中最最外外边边的的双双引引号号本本身身不不是是串串的的内内容容，它它们们是是串串的的标标志志，以以便便将将串串与与标标识识符（如变量名等）加以区别。每个符（
2、如变量名等）加以区别。每个ai（1in）代表一个字符。）代表一个字符。4.1 串的基本概念串的基本概念 当当且且仅仅当当两两个个串串的的长长度度相相等等并并且且各各个个对对应应位位置置上上的的字字符符都都相同时，这两个串才是相同时，这两个串才是相等相等的。的。 一一个个串串中中任任意意个个连连续续字字符符组组成成的的子子序序列列（含含空空串串）称称为为该该串串的的子子串串。例例如如，“a”、“ab”、“abc”和和“abcd”等等都都是是“abcde”的的子串（子串（真子串真子串是指不包含自身的所有子串）。是指不包含自身的所有子串）。思考题：思考题：串和线性表串和线性表有什么异同？有什么异同？
3、例例4.1 问题问题: “abcde”有多少个有多少个真子串真子串?解解:空串数空串数:1含含1个字符的子串数个字符的子串数:5含含2个字符的子串数个字符的子串数:4含含3个字符的子串数个字符的子串数:3含含4个字符的子串数个字符的子串数:2共有共有1+2+3+4+5=15个子串。个子串。推广：推广：含有含有n个相互相同字符的串有个相互相同字符的串有n(n+1)/2个真子串。个真子串。 串的基本运算如下串的基本运算如下: StrAssign(&s,cstr)：将字符串常量将字符串常量cstr赋给串赋给串s，即生，即生成其值等于成其值等于cstr的串的串s。StrCopy(&s,t)：串复制。将
4、串串复制。将串t赋给串赋给串s。StrEqual(s,t)：判串相等。若两个串：判串相等。若两个串s与与t相等则返回真；相等则返回真；否则返回假。否则返回假。StrLength(s)：求串长。返回串求串长。返回串s中字符个数。中字符个数。Concat(s,t)：串连接串连接:返回由两个串返回由两个串s和和t连接在一起形连接在一起形成的新串。成的新串。SubStr(s,i,j)：求子串。返回串求子串。返回串s中从第中从第i（1in）个字）个字符开始的、由连续符开始的、由连续j个字符组成的子串。个字符组成的子串。InsStr(s1,i,s2)：插入。将串插入。将串s2插入到串插入到串s1的第的第i
5、（1in+1）个字符中，即将）个字符中，即将s2的第一个字符作为的第一个字符作为s1的第的第i个字符，并返回产生的新串。个字符，并返回产生的新串。DelStr(s,i,j)：删除。从串删除。从串s中删去从第中删去从第i（1in）个字符开）个字符开始的长度为始的长度为j的子串，并返回产生的新串。的子串，并返回产生的新串。RepStr(s,i,j,t)：替换。在串替换。在串s中，将第中，将第i（1in）个字符开）个字符开始的始的j个字符构成的子串用串个字符构成的子串用串t替换，并返回产生的新串。替换，并返回产生的新串。DispStr(s)：串输出。输出串串输出。输出串s的所有元素值。的所有元素值。
6、4.2.1 串的顺序存储及其基本操作实现串的顺序存储及其基本操作实现 4.2 串的存储结构串的存储结构 在在顺顺序序串串中中，串串中中的的字字符符被被依依次次存存放放在在一一组组连连续续的的存存储储单单元元里里。一一般般来来说说，一一个个字字节节（8位位）可可以以表表示示一一个个字字符符（即该字符的（即该字符的ASCII码）。码）。因因此此，一一个个内内存存单单元元可可以以存存储储多多个个字字符符。例例如如，一一个个32位的内存单元可以存储位的内存单元可以存储4个字符（即个字符（即4个字符的个字符的ASCII码）。码）。 串的顺序存储有两种方法：一种是每个单元只存一个字符，串的顺序存储有两种方
7、法：一种是每个单元只存一个字符，这称为这称为非紧缩格式非紧缩格式（其存储密度小）；另一种是每个单元存放（其存储密度小）；另一种是每个单元存放多个字符，这称为多个字符，这称为紧缩格式紧缩格式（其存储密度大）。（其存储密度大）。 非紧缩格式示例非紧缩格式示例 紧缩格式示例紧缩格式示例 对于非紧缩格式的顺序串，其类型定义如下：对于非紧缩格式的顺序串，其类型定义如下： #define MaxSize 100typedef struct char dataMaxSize; int length; SqString; 其中其中data域用来存储字符串，域用来存储字符串，length域用来存储字符域用来存储
8、字符串的当前长度，串的当前长度，MaxSize常量表示允许所存储字符串的最常量表示允许所存储字符串的最大长度。在大长度。在C语言中每个字符串以语言中每个字符串以0标志结束。标志结束。 顺序串中实现串的基本运算如下。顺序串中实现串的基本运算如下。 （1）StrAssign(s,cstr)将一个字符串常量赋给串将一个字符串常量赋给串s，即生成一个其值等于，即生成一个其值等于cstr的串的串s。void StrAssign(SqString &s,char cstr)/s为引用型参数为引用型参数 int i; for (i=0;cstri!=0;i+)s.datai=cstri; s.length=
9、i;建立顺序串的算法。建立顺序串的算法。（2）StrCopy(s,t)将串将串t复制给串复制给串s。void StrCopy(SqString &s,SqString t)/s为引用型参数为引用型参数 int i; for (i=0;it.length;i+)s.datai=t.datai; s.length=t.length;（3）StrEqual(s,t) 判串相等：若两个串判串相等：若两个串s与与t相等返回真（相等返回真（1）；否则返回假（）；否则返回假（0）。）。bool StrEqual(SqString s,SqString t) bool same=true; int i; if
10、 (s.length!=t.length)/长度不相等时返回长度不相等时返回0same=false; else for (i=0;is.length;i+) if (s.datai!=t.datai) same=false;break; return same;（4）StrLength(s)求串长：返回串求串长：返回串s中字符个数。中字符个数。int StrLength(SqString s) return s.length;（5）Concat(s,t)串连接：返回由两个串串连接：返回由两个串s和和t连接在一起形成的新串。连接在一起形成的新串。SqString Concat(SqString
11、s,SqString t) SqString str; int i; str.length=s.length+t.length; for (i=0;is.length;i+) /s.data0.s.length-1strstr.datai=s.datai; for (i=0;it.length;i+) /t.data0.t.length-1strstr.datas.length+i=t.datai; return str;（6）SubStr(s,i,j) 求子串：返回串求子串：返回串s中从第中从第i（1iStrLength(s)）个字符开始的、）个字符开始的、由连续由连续j个字符组成的子串。参
12、数不正确时返回一个空串。个字符组成的子串。参数不正确时返回一个空串。SqString SubStr(SqString s,int i,int j) SqString str; int k; str.length=0; if (is.length | js.length)return str; /参数不正确时返回空串参数不正确时返回空串 for (k=i-1;ki+j-1;k+) /s.datai.i+jstrstr.datak-i+1=s.datak; str.length=j; return str; （7）InsStr(s1,i,s2) 将串将串s2插入到串插入到串s1的第的第i（1iSt
13、rLength(s)+1）个字符中，）个字符中，即将即将s2的第一个字符作为的第一个字符作为s1的第的第i个字符，并返回产生的新串。参个字符，并返回产生的新串。参数不正确时返回一个空串。数不正确时返回一个空串。SqString InsStr(SqString s1,int i,SqString s2) int j; SqString str; str.length=0; if (is1.length+1) /参数不正确时返回空串参数不正确时返回空串return str; for (j=0;ji-1;j+) /将将s1.data0.i-2strstr.dataj=s1.dataj; for (j
14、=0;js2.length;j+) /s2.data0.s2.length-1strstr.datai+j-1=s2.dataj; for (j=i-1;js1.length;j+) /s1.datai-1.s1.length-1strstr.datas2.length+j=s1.dataj; str.length=s1.length+s2.length; return str;（8）DelStr(s,i,j) 从串从串s中删去第中删去第i（1iStrLength(s)）个字符开始的长度为）个字符开始的长度为j的的子串，并返回产生的新串。参数不正确时返回一个空串。子串，并返回产生的新串。参数不
15、正确时返回一个空串。SqString DelStr(SqString s,int i,int j) int k; SqString str; str.length=0; if (is.length | i+js.length+1) return str; /参数不正确时返回空串参数不正确时返回空串 for (k=0;ki-1;k+) /s.data0.i-2strstr.datak=s.datak; for (k=i+j-1;ks.length;k+) /s.datai+j-1.s.length-1strstr.datak-j=s.datak; str.length=s.length-j; r
16、eturn str;（9）RepStr(s,i,j,t) 在串在串s中，将第中，将第i（1iStrLength(s)）个字符开始的）个字符开始的j个字符构个字符构成的子串用串成的子串用串t替换，并返回产生的新串。参数不正确时返回一替换，并返回产生的新串。参数不正确时返回一个空串。个空串。SqString RepStr(SqString s,int i,int j,SqString t) int k; SqString str; str.length=0; if (is.length | i+j-1s.length) return str; /参数不正确时返回空串参数不正确时返回空串 for (
17、k=0;ki-1;k+)/s.data0.i-2strstr.datak=s.datak; for (k=0;kt.length;k+) /t.data0.t.length-1strstr.datai+k-1=t.datak; for (k=i+j-1;k0) for (i=0;is.length;i+) printf(%c,s.datai);printf(n); 例例4.2 设计顺序串上实现串比较运算设计顺序串上实现串比较运算Strcmp(s,t)的算法。的算法。 解：解：本例的算法思路如下本例的算法思路如下: （1）比较）比较s和和t两个串共同长度范围内的对应字符两个串共同长度范围内的对应
18、字符: 若若s的字符的字符t的字符，返回的字符，返回1； 若若s的字符的字符t的字符，返回的字符，返回-1； 若若s的字符的字符=t的字符的字符,按上述规则继续比较。按上述规则继续比较。 （2）当（）当（1）中对应字符均相同时，比较）中对应字符均相同时，比较s和和t的长度的长度: 两者相等时，返回两者相等时，返回0； s的长度的长度t的长度，返回的长度，返回1； s的长度的长度t的长度，返回的长度，返回-1。int Strcmp(SqString s,SqString t) int i,comlen; if (s.lengtht.length)comlen=s.length;/求求s和和t的共
19、同长度的共同长度 else comlen=t.length; for (i=0;it.datai)return 1;else if (s.datait.length)/streturn 1; else return -1;/sdata=cstri;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(
20、sizeof(LiString); r=s;/r始终指向尾节点始终指向尾节点 while (p!=NULL)/将将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相等则返回真；否则返回假。相等则返回真；否则返回假。bool StrEqual(LiString *s,LiString *t) LiString *p=s-next,*q=t-next; whil
21、e (p!=NULL & q!=NULL & p-data=q-data) p=p-next;q=q-next; if (p=NULL & q=NULL)return true; elsereturn false;（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连接在一起形成的新串。以下采连接在一
22、起形成的新串。以下采用尾插法建立链串用尾插法建立链串str并返回其地址。并返回其地址。LiString *Concat(LiString *s,LiString *t) LiString *str,*p=s-next,*q,*r; str=(LiString *)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!=NU
23、LL)/将将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,i,j) 求子串：返回串求子串：返回串s中从第中从第i（1iStrLength(s)）个字符开始）个字符开始的、由连续的、由连续j个字符组成的子串，参数不正确时返回一个空串。个字符组成的子串，参数不正确时返回一个空串。以下采用尾插法建立链串以下采用尾插法建立链串str并返回其地址。并返回其地址。LiString *SubS
24、tr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建链表的尾节点指向新建链表的尾节点 if (iStrLength(s) | jStrLength(s)return str; /参数不正确时返回空串参数不正确时返回空串 for (k=0;knext; for (k=1;kdata=p-data;r-next=q;r=q;p=p-next; r-next=NULL; return s
25、tr;（7）InsStr(s1,i,s2) 将串将串s2插入到串插入到串s1的第的第i（1iStrLength(s)+1）个字符位置，）个字符位置，即将即将s2的第的第1个字符作为个字符作为s1的第的第i个字符，个字符，s2的第的第2个字符作为个字符作为s1的的第第i+1个字符，等等，并返回产生的新串个字符，等等，并返回产生的新串, 参数不正确时返回一个参数不正确时返回一个空串。以下采用尾插法建立链串空串。以下采用尾插法建立链串str并返回其地址。并返回其地址。LiString *InsStr(LiString *s,int i,LiString *t) int k; LiString *st
26、r,*p=s-next,*p1=t-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建链表的尾节点指向新建链表的尾节点 if (iStrLength(s)+1)return str; /参数不正确时返回空串参数不正确时返回空串 for (k=1;kdata=p-data; r-next=q;r=q; p=p-next; while (p1!=NULL)/将将t的所有节点复制到的所有节点复制到str q=(LiString *)malloc(sizeof(LiString); q-dat
27、a=p1-data; r-next=q;r=q; p1=p1-next; while (p!=NULL)/将将*p及其后的节点复制到及其后的节点复制到str q=(LiString *)malloc(sizeof(LiString); q-data=p-data; r-next=q;r=q; p=p-next; r-next=NULL; return str;（8）DelStr(s,i,j) 从串从串s中删去从第中删去从第i（1iStrLength(s)）个字符开始的长度）个字符开始的长度为为j的子串，并返回产生的新串的子串，并返回产生的新串, 参数不正确时返回一个空串。参数不正确时返回一个空
28、串。以下采用尾插法建立链串以下采用尾插法建立链串str并返回其地址。并返回其地址。LiString *DelStr(LiString *s,int i,int j) int k; LiString *str,*p=s-next,*q,*r; str=(LiString *)malloc(sizeof(LiString); str-next=NULL; r=str;/r指向新建链表的尾节点指向新建链表的尾节点 if (iStrLength(s) | jStrLength(s)return str; /参数不正确时返回空串参数不正确时返回空串 for (k=0;kdata=p-data;r-nex
29、t=q;r=q;p=p-next; for (k=0;knext; while (p!=NULL)/将将*p及其后的节点复制到及其后的节点复制到str q=(LiString *)malloc(sizeof(LiString);q-data=p-data;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替换，并返回产生的新串，参数不正确时返替换，并返回产生的新串，参数不正确时返回一个
30、空串。以下采用尾插法建立链串回一个空串。以下采用尾插法建立链串str并返回其地址。并返回其地址。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(sizeof(LiString); str-next=NULL; r=str;/r指向新建链表的尾节点指向新建链表的尾节点 if (iStrLength(s) | jStrLength(s) return str; /参数不正确时返回空串参数不正确时返
31、回空串 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; while (p!=NULL)/将将*p及其后的节点复制到及其后的节点复制到str q=(LiString *)malloc(sizeof(LiString);q-data=p-data
32、;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 在在链链串串中中,设设计计一一个个算算法法把把最最先先出出现现的的子子串串ab改为改为xyz。 解解：在在串串s中中找找到到最最先先出出现现的的子子串串“ab”，p指指向向data域域值值为为a的
33、的结结点点，其其后后为为data域域值值为为b的的结结点点。将将它它们们的的data域域值值分分别别改改为为x和和z，再再创创建建一一个个data域域值值为为y的的结结点点，将将其其插插入到入到*p之后。本例算法如下之后。本例算法如下:void Repl(LiString *&s) LiString *p=s-next,*q; int find=0; while (p-next!=NULL & find=0) /查找查找ab子串子串 if (p-data=a & p-next-data=b)/找到子串找到子串 p-data=x;p-next-data=z;/替换为替换为xyz q=(LiStr
34、ing *)malloc(sizeof(LiString); 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称为称为模式串模式串，因此定位也称作，因此定位也称作模式匹配模式匹配。 模式匹配成功是指在目标串模式匹配成功是指在目标串s中找到一个模式串中找到一个模式串t；不成；不成功则指目标串功则指目标串
35、s中不存在模式串中不存在模式串t。 4.4.1 Brute-Force算法算法 Brute-Force简称为简称为BF算法，亦称简单匹配算法，其基本算法，亦称简单匹配算法，其基本思路是思路是: 从目标串从目标串s=“s0s1sn-1”的第一个字符开始和模式串的第一个字符开始和模式串t=“t0t1tm-1”中的第一个字符比较，若相等，则继续逐个比较中的第一个字符比较，若相等，则继续逐个比较后续字符；否则从目标串后续字符；否则从目标串s的第二个字符开始重新与模式串的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推的第一个字符进行比较。依次类推,若从模式串若从模式串s的第的第i个字符个字符
36、开始，每个字符依次和目标串开始，每个字符依次和目标串t中的对应字符相等，则匹配成中的对应字符相等，则匹配成功功,该算法返回该算法返回i；否则，匹配失败，函数返回；否则，匹配失败，函数返回-1。 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);算法算法
37、1 1int index(SqString s,SqString t) int i=0,j=0; while (is.length & j=t.length)return(i-t.length);/返回匹配的第一个字符的下标返回匹配的第一个字符的下标 elsereturn(-1);/模式匹配不成功模式匹配不成功算法算法2 2 例如，设目标串例如，设目标串s=“aaaaab”，模式串，模式串t=“aaab”。s的长度的长度为为n（n=6），），t的长度为的长度为m（m=4）。用指针）。用指针i指示目标串指示目标串s的的当前比较字符位置，用指针当前比较字符位置，用指针j指示模式串指示模式串t的当前
38、比较字符位的当前比较字符位置。模式匹配过程如下图所示。置。模式匹配过程如下图所示。 这个算法简单，易于理解，但效率不高，主要原因是主串这个算法简单，易于理解，但效率不高，主要原因是主串指针指针i在若干个字符序列比较相等后，若有一个字符比较不相在若干个字符序列比较相等后，若有一个字符比较不相等，仍需回溯（即等，仍需回溯（即i=i-j+1）。）。 该算法在最好情况下的时间复杂度为该算法在最好情况下的时间复杂度为O(m)，即主串的前，即主串的前m个字符正好等于模式串的个字符正好等于模式串的m个字符。在最坏情况下的时间复杂个字符。在最坏情况下的时间复杂度为度为O(n*m)。 4.3.2 KMP算法算法
39、 KMP算法是算法是D.E.Knuth、J.H.Morris和和V.R.Pratt共共同提出的，简称同提出的，简称KMP算法算法。该算法较。该算法较BF算法有较大改进，算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。程度的提高。目标串目标串s=aaaaab，模式串，模式串t=aaab。 a a a a a b0 1 2 3 4 5a a a b0 1 2 3 BF算法下一步是从算法下一步是从s1开始开始其实没有必要从其实没有必要从s1开始，为什么？开始，为什么？a a a a a b0 1 2 3 4 5a a a
40、 b0 1 2 3 a a a a a b0 1 2 3 4 5a a a b0 1 2 3 应有一个数组应有一个数组next，使，使next3=2模式串中究竟是什么信息呢？模式串中究竟是什么信息呢？a a a a a b0 1 2 3 4 5a a a b0 1 2 3 nexti是指下标为是指下标为i的字符前有多少个的字符前有多少个真子串真子串的字符。的字符。 所所谓谓真真子子串串是是指指模模式式串串t存存在在某某个个k（0kj），使使得得t0t1tk = tj-ktj-k+1tj 成立。成立。 例如，例如，t= abab, 即即t0t1t2t3 也就是说，也就是说， “ab”是真子串。是
41、真子串。 真真子子串串就就是是模模式式串串中中隐隐藏藏的的信信息息，利利用用它它来来提提高高模模式式匹匹配配的效率。的效率。模式串模式串t=“abcac”，用，用next数组存放这些数组存放这些“部分匹配部分匹配”信息信息 。j01234tjabcacnextj-10001 归纳起来，定义归纳起来，定义nextj函数如下函数如下: maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1” 当此集合非空时当此集合非空时 -1 当当j=0时时 0 其他情况其他情况nextj=j0123tjababnextj-1001t=“abab”对应的对应的next数组如下数组如下:void
42、 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) j+;k+; nextj=k;else k=nextk; 由模式串由模式串t求出求出next值：值：int KMPIndex(SqString s,SqString t) int nextMaxSize,i=0,j=0; GetNext(t,next); while (is.length & j=t.length)return(i-t.length);/返回匹配模式串的首字符下标返回匹
43、配模式串的首字符下标 elsereturn(-1);/返回不匹配标志返回不匹配标志KMP算法：算法： 设主串设主串s的长度为的长度为n，子串，子串t长度为长度为m。 在在KMP算算法法中中求求next数数组组的的时时间间复复杂杂度度为为O(m)，在在后后面面的的匹匹配配中中因因主主串串s的的下下标标不不减减即即不不回回溯溯，比比较较次次数数可可记记为为n，所以，所以KMP算法总的时间复杂度为算法总的时间复杂度为O(n+m)。j01234tjaaaabnextj-10123 上述定义的上述定义的next在某些情况下尚有缺陷。在某些情况下尚有缺陷。 例如，模式例如，模式“aaaab”在和主串在和主
44、串“aaabaaaab”匹配时：匹配时：当当i=3,j=3时，时，s.data3t.data3,由由nextj的指示还需进行的指示还需进行i=3、j=2,i=3、j=1,i=3、j=0等等3次比较。次比较。实际上，因为模式中的第实际上，因为模式中的第1、2、3个字符和第个字符和第4个字符都相个字符都相等，因此不需要再和主串中第等，因此不需要再和主串中第4个字符相比较，而可以将模式个字符相比较，而可以将模式一次向右滑动一次向右滑动4个字符的位置直接进行个字符的位置直接进行i=4，j=0时的字符比较。时的字符比较。 这就是说，若按上述定义得到这就是说，若按上述定义得到nextj=k，而模式中，而模
45、式中tj=tk，则为主串中字符则为主串中字符si和和tj比较不等时，不需要再和比较不等时，不需要再和tk进行比较，而进行比较，而直接和直接和tnextk进行比较。换句话说，此时的进行比较。换句话说，此时的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.l
46、ength) if (k=-1 | t.dataj=t.datak) j+;k+; if (t.dataj!=t.datak) nextvalj=k; elsenextvalj=nextvalk;else k=nextvalk; 由模式串由模式串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); elsereturn(-1);修改后的修改后的KMP算法算法:j01234tjaaaabnextj-10123nextvalj-1-1-1-13思考题：思考题： KMP算法给我们什么启示？算法给我们什么启示？本章小结本章小结 本章基本学习要点如下本章基本学习要点如下: （1）理解串和一般线性表之间的差异。）理解串和一般线性表之间的差异。 （2）重重点点掌掌握握在在顺顺序序串串上上和和链链串串上上实实现现串串的的基基本本运运算算算算法。法。 （3）掌握串的模式匹配算法。）掌握串的模式匹配算法。 （4）灵活运用串这种数据结构解决一些综合应用问题。）灵活运用串这种数据结构解决一些综合应用问题。练习题练习题4 习题习题4.1、4.2和和4.3。
