数据结构第3版第4章串专业教育

《数据结构第3版第4章串专业教育》由会员分享，可在线阅读，更多相关《数据结构第3版第4章串专业教育（66页珍藏版）》请在装配图网上搜索。

1、第第4章章 串串 4.1 串的基本概念串的基本概念4.2 串的存储结构串的存储结构 本章小结本章小结4.3 串的模式匹配串的模式匹配 1高等课堂 串串（或字符串），是由零个或多个（或字符串），是由零个或多个字符字符组成的组成的有穷序列有穷序列。含零个字符的串称为空串，用含零个字符的串称为空串，用表示。表示。 串中所含字符的个数称为该串中所含字符的个数称为该串的长度串的长度（或串长）。（或串长）。 通常将一个串表示成通常将一个串表示成“a1a2an”的形式。其中最外边的双的形式。其中最外边的双引号本身不是串的内容，它们是串的标志，以便将串与标识引号本身不是串的内容，它们是串的标志，以便将串与标识

2、符（如变量名等）加以区别。每个符（如变量名等）加以区别。每个ai（1in）代表一个字符。）代表一个字符。4.1 串的基本概念串的基本概念2高等课堂 当且仅当两个串的长度相等并且各个对应位置上的字符都当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相同时，这两个串才是相等相等的。的。 一个串中任意个连续字符组成的一个串中任意个连续字符组成的子序列子序列（含空串）称为该（含空串）称为该串的子串。例如，串的子串。例如，“a”、“ab”、“abc”和和“abcd”等都是等都是“abcde”的子串（的子串（真子串真子串是指不包含自身的所有子串）。是指不包含自身的所有子串）。3高等课

3、堂思考题：思考题：串和线性表串和线性表有什么异同？有什么异同？4高等课堂例例4.1 问题问题: “abcde”有多少个有多少个真子串真子串?解解:空串数空串数:1含含1个字符的子串数个字符的子串数:5含含2个字符的子串数个字符的子串数:4含含3个字符的子串数个字符的子串数:3含含4个字符的子串数个字符的子串数:2共有共有1+2+3+4+5=15个子串。个子串。推广：推广：含有含有n个相互相同字符的串有个相互相同字符的串有n(n+1)/2个真子串。个真子串。5高等课堂 串的基本运算如下串的基本运算如下: StrAssign(&s,cstr)：将字符串常量将字符串常量cstr赋给串赋给串s，即生，

4、即生成其值等于成其值等于cstr的串的串s。StrCopy(&s,t)：串复制。将串串复制。将串t赋给串赋给串s。StrEqual(s,t)：判串相等。若两个串：判串相等。若两个串s与与t相等则返回真；相等则返回真；否则返回假。否则返回假。StrLength(s)：求串长。返回串求串长。返回串s中字符个数。中字符个数。Concat(s,t)：串连接串连接:返回由两个串返回由两个串s和和t连接在一起形连接在一起形成的新串。成的新串。SubStr(s,i,j)：求子串。返回串求子串。返回串s中从第中从第i（1in）个字）个字符开始的、由连续符开始的、由连续j个字符组成的子串。个字符组成的子串。6高

5、等课堂InsStr(s1,i,s2)：插入。将串插入。将串s2插入到串插入到串s1的第的第i（1in+1）个字符中，即将个字符中，即将s2的第一个字符作为的第一个字符作为s1的第的第i个字符，并返个字符，并返回产生的新串。回产生的新串。DelStr(s,i,j)：删除。从串删除。从串s中删去从第中删去从第i（1in）个字符开）个字符开始的长度为始的长度为j的子串，并返回产生的新串。的子串，并返回产生的新串。RepStr(s,i,j,t)：替换。在串替换。在串s中，将第中，将第i（1in）个字符开）个字符开始的始的j个字符构成的子串用串个字符构成的子串用串t替换，并返回产生的新串。替换，并返回产

6、生的新串。DispStr(s)：串输出。输出串串输出。输出串s的所有元素值。的所有元素值。7高等课堂4.2.1 串的顺序存储及其基本操作实现串的顺序存储及其基本操作实现 4.2 串的存储结构串的存储结构 在顺序串中，串中的字符被依次存放在一组连续的存在顺序串中，串中的字符被依次存放在一组连续的存储单元里。一般来说，一个字节（储单元里。一般来说，一个字节（8位）可以表示一个字符位）可以表示一个字符（即该字符的（即该字符的ASCII码）。码）。因此，一个内存单元可以存储多个字符。例如，一个因此，一个内存单元可以存储多个字符。例如，一个32位的内存单元可以存储位的内存单元可以存储4个字符（即个字符（

7、即4个字符的个字符的ASCII码）。码）。 8高等课堂串的顺序存储有两种方法：一种是每个单元只存一个字符，串的顺序存储有两种方法：一种是每个单元只存一个字符，这称为这称为非紧缩格式非紧缩格式（其存储密度小）；另一种是每个单元存放（其存储密度小）；另一种是每个单元存放多个字符，这称为多个字符，这称为紧缩格式紧缩格式（其存储密度大）。（其存储密度大）。 A B C D E F G H I J K L M N 1001 1002 1003 1004 1005 1006 1007 1008 1009 100a 100b 100c 100d 100e A B C D E F G H I J K L M

8、N 1000 1001 1002 1003 非紧缩格式示例非紧缩格式示例 紧缩格式示例紧缩格式示例 9高等课堂对于非紧缩格式的顺序串，其类型定义如下：对于非紧缩格式的顺序串，其类型定义如下： #define MaxSize 100typedef struct char dataMaxSize; int length; SqString; 其中其中data域用来存储字符串，域用来存储字符串，length域用来存储字符域用来存储字符串的当前长度，串的当前长度，MaxSize常量表示允许所存储字符串的最常量表示允许所存储字符串的最大长度。在大长度。在C语言中每个字符串以语言中每个字符串以0标志结束。

9、标志结束。10高等课堂 顺序串中实现串的基本运算如下。顺序串中实现串的基本运算如下。 （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=i;建立顺序串的算法。建立顺序串的算法。11高等课堂（2）StrCopy(s,t)将串将串t复制给串复制给串s。void StrCopy(SqString &s

10、,SqString t)/s为引用型参数为引用型参数 int i; for (i=0;it.length;i+)s.datai=t.datai; s.length=t.length;12高等课堂（3）StrEqual(s,t) 判串相等：若两个串判串相等：若两个串s与与t相等返回真（相等返回真（1）；否则返回假（）；否则返回假（0）。）。bool StrEqual(SqString s,SqString t) bool same=true; int i; if (s.length!=t.length)/长度不相等时返回长度不相等时返回0same=false; else for (i=0;is.

11、length;i+) if (s.datai!=t.datai) same=false;break; return same;13高等课堂（4）StrLength(s)求串长：返回串求串长：返回串s中字符个数。中字符个数。int StrLength(SqString s) return s.length;14高等课堂（5）Concat(s,t)串连接：返回由两个串串连接：返回由两个串s和和t连接在一起形成的新串。连接在一起形成的新串。SqString Concat(SqString s,SqString t) SqString str; int i; str.length=s.length+t

12、.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;15高等课堂（6）SubStr(s,i,j) 求子串：返回串求子串：返回串s中从第中从第i（1iStrLength(s)）个字符开始的、）个字符开始的、由连续由连续j个字符组成的子串。参数不正确时返回一个空串。个字符组成的子串。参数不正确时返回一个空串。SqString SubStr(

13、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; 16高等课堂（7）InsStr(s1,i,s2) 将串将串s2插入到串插入到串s1的第的第i（1iStrLength(s)+1）个字符中，）个字符中，即将即将s2的第一个字符作为的第一个字符

14、作为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=0;js2.length;j+) /s2.data0.s2.length-1strst

15、r.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;17高等课堂（8）DelStr(s,i,j) 从串从串s中删去第中删去第i（1iStrLength(s)）个字符开始的长度为）个字符开始的长度为j的的子串，并返回产生的新串。参数不正确时返回一个空串。子串，并返回产生的新串。参数不正确时返回一个空串。SqString DelStr(SqString s,i

16、nt 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; return str;18高等课堂（9）RepStr(s,i,j,t) 在串在

17、串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 (k=0;ki-1;k+)/s.data0.i-2strstr.d

18、atak=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); 20高等课堂例例4.2 设计顺序串上实现串比较运算设计顺序串上实现串比较运算Strcmp(s,t)的算法。的算法。 解：解：本例的算法思路如下本例的算法思路如下: （1）比较）比较s和和t两个串共同长度范围内的对应字符两个串共同长度范围内的对应字符: 若若s的字符的字符t的字符，返回的字符，返回

19、1； 若若s的字符的字符t的字符，返回的字符，返回-1； 若若s的字符的字符=t的字符的字符,按上述规则继续比较。按上述规则继续比较。 （2）当（）当（1）中对应字符均相同时，比较）中对应字符均相同时，比较s和和t的长度的长度: 两者相等时，返回两者相等时，返回0； s的长度的长度t的长度，返回的长度，返回1； s的长度的长度t的长度，返回的长度，返回-1。21高等课堂int Strcmp(SqString s,SqString t) int i,comlen; if (s.lengtht.length)comlen=s.length;/求求s和和t的共同长度的共同长度 else comlen

20、=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;26高等课堂（2）StrCopy(s,t) 将串将串t复制给串复制给串s。以下采用尾插法建立复制后的链串。以下采用尾插法建立复制后的链串s。void StrCopy(LiString *&s,LiString *t) LiString *p=t-next,*q,*r; s=(LiString *)malloc(sizeof(LiStrin

21、g); 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;27高等课堂（3）StrEqual(s,t)判串相等：若两个串判串相等：若两个串s与与t相等则返回真；否则返回假。相等则返回真；否则返回假。bool StrEqual(LiString *s,LiString *t) LiString *p=s-next,*q=t-next; while (p!=NU

22、LL & q!=NULL & p-data=q-data) p=p-next;q=q-next; if (p=NULL & q=NULL)return true; elsereturn false;28高等课堂（4）StrLength(s)求串长：返回串求串长：返回串s中字符个数。中字符个数。int StrLength(LiString *s) int i=0; LiString *p=s-next; while (p!=NULL) i+;p=p-next; return i;29高等课堂（5）Concat(s,t) 串连接：返回由两个串串连接：返回由两个串s和和t连接在一起形成的新串。以下采

23、连接在一起形成的新串。以下采用尾插法建立链串用尾插法建立链串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;30高等课堂 wh

24、ile (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;31高等课堂（6）SubStr(s,i,j) 求子串：返回串求子串：返回串s中从第中从第i（1iStrLength(s)）个字符开始）个字符开始的、由连续的、由连续j个字符组成的子串，参数不正确时返回一个空串。个字符组成的子串，参数不正确时返回一个空串。以下采用尾插法建立链串以下采用尾插法建立链串str并返回其地址。并返回其地

25、址。LiString *SubStr(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;32高等课堂 for (k=1;kdata=p-data;r-next=q;r=q;p=p-next;

26、 r-next=NULL; return str;33高等课堂（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,LiSt

27、ring *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)+1)return str; /参数不正确时返回空串参数不正确时返回空串34高等课堂 for (k=1;kdata=p-data; r-next=q;r=q; p=p-next; while (p1!=NULL)/将将t的所有节点复制到的所有节点复制到str q=(LiStrin

28、g *)malloc(sizeof(LiString); q-data=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;35高等课堂（8）DelStr(s,i,j) 从串从串s中删去从第中删去从第i（1iStrLength(s)）个字符开始的长度）个字符开始的长度为为j的子串，并返回产生的

29、新串的子串，并返回产生的新串, 参数不正确时返回一个空串。参数不正确时返回一个空串。以下采用尾插法建立链串以下采用尾插法建立链串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; /参数不正确时返回

30、空串参数不正确时返回空串36高等课堂 for (k=0;kdata=p-data;r-next=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;37高等课堂（9）RepStr(s,i,j,t) 在串在串s中，将第中，将第i（1iStrLength(s)）个字符开始的）个字符开始的j个字符个字符构成的子

31、串用串构成的子串用串t替换，并返回产生的新串，参数不正确时返替换，并返回产生的新串，参数不正确时返回一个空串。以下采用尾插法建立链串回一个空串。以下采用尾插法建立链串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 (iStrLeng

32、th(s) | jStrLength(s) return str; /参数不正确时返回空串参数不正确时返回空串38高等课堂 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及其后的节点复制到及其后的节点

33、复制到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;39高等课堂（10）DispStr(s)输出串输出串s的所有元素值。的所有元素值。void DispStr(LiString *s) LiString *p=s-next; while (p!=NULL) printf(%c,p-data);p=p-next; printf(n);40高等课堂 例例4.3 在链串中在链串中,设计一个算法把最先出现的子串设计一个算

34、法把最先出现的子串ab改为改为xyz。 解：解：在串在串s中找到最先出现的子串中找到最先出现的子串“ab”，p指向指向data域值域值为为a的结点，其后为的结点，其后为data域值为域值为b的结点。将它们的的结点。将它们的data域值分别改为域值分别改为x和和z，再创建一个，再创建一个data域值为域值为y的结点，的结点，将其插入到将其插入到*p之后。本例算法如下之后。本例算法如下:41高等课堂void Repl(LiString *&s) LiString *p=s-next,*q; int find=0; while (p-next!=NULL & find=0) /查找查找ab子串子串

35、if (p-data=a & p-next-data=b)/找到子串找到子串 p-data=x;p-next-data=z;/替换为替换为xyz q=(LiString *)malloc(sizeof(LiString); q-data=y;q-next=p-next;p-next=q; find=1;else p=p-next; 42高等课堂4.3 串的模式匹配串的模式匹配 设有主串设有主串s和子串和子串t，子串，子串t的定位就是要在主串的定位就是要在主串s中找到中找到一个与子串一个与子串t相等的子串。通常把主串相等的子串。通常把主串s称为称为目标串目标串，把子串，把子串t称为称为模式串模式

36、串，因此定位也称作，因此定位也称作模式匹配模式匹配。 模式匹配成功是指在目标串模式匹配成功是指在目标串s中找到一个模式串中找到一个模式串t；不成；不成功则指目标串功则指目标串s中不存在模式串中不存在模式串t。 43高等课堂4.4.1 Brute-Force算法算法 Brute-Force简称为简称为BF算法，亦称简单匹配算法，其基本算法，亦称简单匹配算法，其基本思路是思路是: 从目标串从目标串s=“s0s1sn-1”的第一个字符开始和模式串的第一个字符开始和模式串t=“t0t1tm-1”中的第一个字符比较，若相等，则继续逐个比中的第一个字符比较，若相等，则继续逐个比较后续字符；否则从目标串较后

37、续字符；否则从目标串s的第二个字符开始重新与模式串的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推的第一个字符进行比较。依次类推,若从模式串若从模式串s的第的第i个字符个字符开始，每个字符依次和目标串开始，每个字符依次和目标串t中的对应字符相等，则匹配成中的对应字符相等，则匹配成功功,该算法返回该算法返回i；否则，匹配失败，函数返回；否则，匹配失败，函数返回-1。 44高等课堂int indexpos(SqString str,SqString substr) int i,j,k,idx=-1; for (i=0;istr.length;i+) for (j=i,k=0;str.d

38、ataj=substr.datak; j+,k+); if (k=substr.length) /注意注意j每次从每次从i开始开始,有回溯有回溯 return(i); return(-1);算法算法1 145高等课堂int index(SqString s,SqString t) int i=0,j=0; while (is.length & j=t.length)return(i-t.length);/返回匹配的第一个字符的下标返回匹配的第一个字符的下标 elsereturn(-1);/模式匹配不成功模式匹配不成功算法算法2 246高等课堂 例如，设目标串例如，设目标串s=“aaaaab”，

39、模式串，模式串t=“aaab”。s的长度的长度为为n（n=6），），t的长度为的长度为m（m=4）。用指针）。用指针i指示目标串指示目标串s的的当前比较字符位置，用指针当前比较字符位置，用指针j指示模式串指示模式串t的当前比较字符位的当前比较字符位置。模式匹配过程如下图所示。置。模式匹配过程如下图所示。 第 1 趟匹配 s=a a a a a b i=3 t=a a a b j=3 失败,修改为 第 2 趟匹配 s=a a a a a b i=4 t=a a a b j=3 第 3 趟匹配 s=a a a a a b i=6 t=a a a b j=4 成功，返回 i-t.length=2 i

40、=i-j+1=1 j=0 失败,修改为 i=i-j+1=2 j=0 47高等课堂 这个算法简单，易于理解，但效率不高，主要原因是主串这个算法简单，易于理解，但效率不高，主要原因是主串指针指针i在若干个字符序列比较相等后，若有一个字符比较不相在若干个字符序列比较相等后，若有一个字符比较不相等，仍需回溯（即等，仍需回溯（即i=i-j+1）。）。 该算法在最好情况下的时间复杂度为该算法在最好情况下的时间复杂度为O(m)，即主串的前，即主串的前m个字符正好等于模式串的个字符正好等于模式串的m个字符。在最坏情况下的时间复杂个字符。在最坏情况下的时间复杂度为度为O(n*m)。 48高等课堂 4.3.2 K

41、MP算法算法 KMP算法是算法是D.E.Knuth、J.H.Morris和和V.R.Pratt共同共同提出的，简称提出的，简称KMP算法算法。该算法较。该算法较BF算法有较大改进，主算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。度的提高。49高等课堂目标串目标串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

42、2 3 4 5a a a b0 1 2 3 a a a a a b0 1 2 3 4 5a a a b0 1 2 3 应有一个数组应有一个数组next，使使next3=250高等课堂模式串中究竟是什么信息呢？模式串中究竟是什么信息呢？a a a a a b0 1 2 3 4 5a a a b0 1 2 3 nexti是指下标为是指下标为i的字符前有多少个的字符前有多少个真子串真子串的字符。的字符。51高等课堂 所谓所谓真子串真子串是指模式串是指模式串t存在某个存在某个k（0kj），使得），使得t0t1tk = tj-ktj-k+1tj 成立。成立。 例如，例如，t= abab, 即即t0t1t

43、2t3 也就是说，也就是说， “ab”是真子串。是真子串。 真子串就是模式串中隐藏的信息，利用它来提高模式匹配真子串就是模式串中隐藏的信息，利用它来提高模式匹配的效率。的效率。52高等课堂模式串模式串t=“abcac”，用，用next数组存放这些数组存放这些“部分匹配部分匹配”信息信息 。j01234tjabcacnextj-1000153高等课堂 归纳起来，定义归纳起来，定义nextj函数如下函数如下: maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1” 当此集合非空时当此集合非空时 -1 当当j=0时时 0 其他情况其他情况nextj=j0123tjababnex

44、tj-1001t=“abab”对应的对应的next数组如下数组如下:54高等课堂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) j+;k+; nextj=k;else k=nextk; 由模式串由模式串t求出求出next值：值：55高等课堂int KMPIndex(SqString s,SqString t) int nextMaxSize,i=0,j=0; GetNext(t,next); while (is.length

45、 & j=t.length)return(i-t.length);/返回匹配模式串的首字符下标返回匹配模式串的首字符下标 elsereturn(-1);/返回不匹配标志返回不匹配标志KMP算法：算法：56高等课堂 设主串设主串s的长度为的长度为n，子串，子串t长度为长度为m。 在在KMP算法中求算法中求next数组的时间复杂度为数组的时间复杂度为O(m)，在后，在后面的匹配中因主串面的匹配中因主串s的下标不减即不回溯，比较次数可记为的下标不减即不回溯，比较次数可记为n，所以所以KMP算法总的时间复杂度为算法总的时间复杂度为O(n+m)。57高等课堂 第第 1 1 次匹配次匹配 s=aaabaa

46、aab i=3 t=aaaab j=3,j=next3=2 失败失败 第第 2 2 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=2,j=next2=1 失败失败 第第 3 3 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=1,j=next1=0 失败失败 第第 4 4 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=0,j=next0=- -1 失败失败 第第 5 5 次匹配次匹配 s=aaabaaaab i=9 t=aaaab j=5,返回返回 9- -5=4 成功成功 j01234tjaaaabnextj-1012358高等课堂

47、上述定义的上述定义的next在某些情况下尚有缺陷。在某些情况下尚有缺陷。 例如，模式例如，模式“aaaab”在和主串在和主串“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=

48、4，j=0时的字符比较。时的字符比较。 59高等课堂 这就是说，若按上述定义得到这就是说，若按上述定义得到nextj=k，而模式中，而模式中tj=tk，则为主串中字符则为主串中字符si和和tj比较不等时，不需要再和比较不等时，不需要再和tk进行比较，而进行比较，而直接和直接和tnextk进行比较。换句话说，此时的进行比较。换句话说，此时的nextj应和应和nextk相同。相同。 为此将为此将nextj修正为修正为nextvalj： 比较比较t.dataj和和t.datak，若不等，则，若不等，则 nextvalj=nextj；若相等若相等nextvalj=nextvalk。60高等课堂void

49、 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; elsenextvalj=nextvalk;else k=nextvalk; 由模式串由模式串t求出求出nextval值：值：61高等课堂int KMPIndex1(SqString s,SqString t) int nextvalMaxSize,i=0,j=0; GetNextval(t,nex

50、tval); while (is.length & j=t.length)return(i-t.length); elsereturn(-1);修改后的修改后的KMP算法算法:62高等课堂j01234tjaaaabnextj-10123nextvalj-1-1-1-13 第第 1 1 次匹配次匹配 s=aaabaaaab i=3 t=aaaab j=3,j=nextval3=-1 失败失败 第第 2 2 次匹配次匹配 s=aaabaaaab i=9 t=aaaab j=5,返回返回 9-5=4 成功成功 63高等课堂思考题：思考题： KMP算法给我们什么启示？算法给我们什么启示？64高等课堂本章小结本章小结 本章基本学习要点如下本章基本学习要点如下: （1）理解串和一般线性表之间的差异。）理解串和一般线性表之间的差异。 （2）重点掌握在顺序串上和链串上实现串的基本运算算）重点掌握在顺序串上和链串上实现串的基本运算算法。法。 （3）掌握串的模式匹配算法。）掌握串的模式匹配算法。 （4）灵活运用串这种数据结构解决一些综合应用问题。）灵活运用串这种数据结构解决一些综合应用问题。65高等课堂练习题练习题4 习题习题4.1、4.2和和4.3。66高等课堂