《最新【考研计算机专业课】武汉大学数据结构PPT课件 第4章串(共83张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】武汉大学数据结构PPT课件 第4章串(共83张PPT课件).pptx（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第4章章 串串 4.1 4.1 串的基本概念串的基本概念4.2 4.2 串的存储串的存储(cn ch)(cn ch)结构结构 4.3 4.3 串的模式匹配串的模式匹配 数据结构数据结构(sh j ji u)基础第基础第2章章2.7节节p6871第一页，共八十三页。 串串(或字符串或字符串),是由零个或多个字符组成的有穷序列。含零个字符的是由零个或多个字符组成的有穷序列。含零个字符的串称为空串串称为空串,用用表示。表示。 串中所含字符的个数称为该串的串中所含字符的个数称为该串的长度长度(或串长或串长)。 通常将一个串表示成通常将一个串表示成a1a2an的形式。其中的形式。其中,最外边的双引号本
2、身最外边的双引号本身不是不是(b shi)串的内容串的内容,它们是串的标志它们是串的标志,以便将串与标识符以便将串与标识符(如变量名等如变量名等)加以加以区别。每个区别。每个ai(1in)代表一个字符。代表一个字符。4.1 4.1 串的基本概念串的基本概念第二页，共八十三页。 当且仅当当且仅当两个串的长度相等两个串的长度相等并且各个对应位置上的字符都相同时并且各个对应位置上的字符都相同时,这两个串才是相等的。这两个串才是相等的。 一个串中任意个连续字符组成的子序列一个串中任意个连续字符组成的子序列(xli)(含空串含空串,但不含串但不含串本身本身)称为该串的子串。例如称为该串的子串。例如,“a
3、”、“ab”、“abc”和和“abcd”等都是等都是“abcde”的的子串子串（真子串真子串是指不包含自身的所有子串）。是指不包含自身的所有子串）。第三页，共八十三页。思考题：思考题：串和线性表串和线性表有什么有什么(shn me)异同？异同？第四页，共八十三页。例例4.1 问题问题(wnt): “abcde”有多少个真子串有多少个真子串?解解:空串数空串数:1含含1个字符的子串数个字符的子串数:5含含2个字符的子串数个字符的子串数:4含含3个字符的子串数个字符的子串数:3含含4个字符的子串数个字符的子串数:2共有共有(n yu)1+2+3+4+5=15个子串。个子串。第五页，共八十三页。 串
4、的基本运算如下串的基本运算如下: （1）StrAssign(&s,chars):将一个字符串常量赋给串将一个字符串常量赋给串s,即生成一个其即生成一个其值等于值等于chars的串的串s。 （2）StrCopy(&s,t):串复制串复制:将串将串t赋给串赋给串s。 （3）StrEqual(s,t):判串相等判串相等(xingdng):若两个串若两个串s与与t相等相等(xingdng)则返回则返回真；否则返回假。真；否则返回假。 （4）StrLength(s):求串长求串长:返回串返回串s中字符个数。中字符个数。第六页，共八十三页。 （5）Concat(s,t):串连接串连接:返回由两个串返回由两
5、个串s和和t连接在一起形成连接在一起形成(xngchng)的新串。的新串。 （6）SubStr(s,i,j):求子串求子串:返回串返回串s中从第中从第i(1iStrLength(s)个字符开始的、由连续个字符开始的、由连续j个字符组成的子串。个字符组成的子串。 （7）InsStr(s1,i,s2):将串将串s2插入到串插入到串s1的第的第i(1iStrLength(s)+1)个字符中个字符中,即将即将s2的第一个字符作为的第一个字符作为s1的第的第i个字符个字符,并返回产生的新串。并返回产生的新串。第七页，共八十三页。 （8）DelStr(s,i,j):从串从串s中删去中删去(shn q)从第
6、从第i(1iStrLength(s)个字符开始的长度为个字符开始的长度为j的子串的子串,并返回产生的新串。并返回产生的新串。 （9）RepStr(s,i,j,t):替换替换:在串在串s中中,将第将第i(1iStrLength(s)个字个字符开始的符开始的j个字符构成的子串用串个字符构成的子串用串t替换替换,并返回产生的新串。并返回产生的新串。 （10）DispStr(s):串输出串输出:输出串输出串s的所有元素值。的所有元素值。第八页，共八十三页。4.2.1 4.2.1 串的顺序存储及其基本操作实现串的顺序存储及其基本操作实现 串是一种特殊的线性表串是一种特殊的线性表,在非紧缩格式中在非紧缩格
7、式中,它的每个结点仅由一个字符它的每个结点仅由一个字符组成组成,因此存储串的方法因此存储串的方法(fngf)也就是存储线性表的一般方法也就是存储线性表的一般方法(fngf)。存储。存储串最常用的方式是采用顺序存储串最常用的方式是采用顺序存储,即把串的字符顺序地存储在内存一片相即把串的字符顺序地存储在内存一片相邻的空间邻的空间,这称为这称为顺序串顺序串。4.2 4.2 串的存储串的存储(cn ch)(cn ch)结构结构 第九页，共八十三页。 顺序存储采用一般顺序表的存储结构顺序存储采用一般顺序表的存储结构(jigu),其类型定义如下其类型定义如下: #define MaxSize 100 ty
8、pedef struct char dataMaxSize; int length; SqString; 其中其中,data域用来存储字符串域用来存储字符串,length域用来存储字符串的当前长域用来存储字符串的当前长度度,MaxSize常量表示允许所存储字符串的最大长度。在常量表示允许所存储字符串的最大长度。在C语言中每语言中每个字符串以个字符串以0标志结束。标志结束。第十页，共八十三页。 顺序串中实现顺序串中实现(shxin)串的基本运算如下串的基本运算如下: （1）StrAssign(str,cstr) 将一个字符串常量赋给串将一个字符串常量赋给串str,即生成一个其值等于即生成一个其值
9、等于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复制复制(fzh)给串给串s。void StrCopy(SqString &s,SqString t) /引用型参数引用型参数 int i; for (i=0;it.length;i+) s.datai=t.datai; s.length=t.length;第十二页，共八十三页。 （3）StrEqual(s
10、,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) /有一个有一个(y )对应字符不同时返回对应字符不同时返回0 same=0; break; return same; 第十三页，共八十三页。 （4）StrLength(
11、s)求串长求串长:返回返回(fnhu)串串s中字符个数。中字符个数。int StrLength(SqString s) return s.length;第十四页，共八十三页。 （5）Concat(s,t) 返回由两个返回由两个(lin )串串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
12、+) str.datas.length+i=t.datai; return str; 第十五页，共八十三页。 （6）SubStr(s,i,j) 返回串返回串s中从第中从第i(1iStrLength(s)个字符开始的、由连续个字符开始的、由连续j个字符个字符组成组成(z chn)的子串。的子串。 SqString SubStr(SqString s,int i,int j) SqString str;int k;str.length=0; if (is.length | js.length) printf(参数不正确参数不正确n); return str; /参数不正确时返回空串参数不正确时返回
13、空串 for (k=i-1;ki+j-1;k+) str.datak-i+1=s.datak; str.length=j; return str; 第十六页，共八十三页。 （7）InsStr(s1,i,s2) 将串将串s2插入到串插入到串s1的第的第i个字符个字符(z f)中中,即将即将s2的第一个字符的第一个字符(z f)作为作为s1的第的第i个字符个字符(z f),并返回产生的新串。并返回产生的新串。 SqString InsStr(SqString s1,int i,SqString s2) int j; SqString str; str.length=0; if (is1.lengt
14、h+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 (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)个字符开始的长度
15、为个字符开始的长度为j的子串的子串,并返回产并返回产生的新串。生的新串。 SqString DelStr(SqString s,int i,int j) int k;SqString str; str.length=0; if (is.length | i+js.length+1) /参数参数(cnsh)不正确时返回空串不正确时返回空串 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; s
16、tr.length=s.length-j; return str; 第二十页，共八十三页。 （9）RepStr(s,i,j,t) 在串在串s中中,将第将第i(1iStrLength(s)个字符开始的个字符开始的j个字符构成的子串用串个字符构成的子串用串t替换替换,并返回产生并返回产生(chnshng)的新串。的新串。SqString RepStr(SqString s,int i,int j,SqString t) int k;SqString str; str.length=0; if (is.length | i+j-1s.length) /参数不正确时返回空串参数不正确时返回空串 pri
17、ntf(参数不正确参数不正确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的字符的字符,按上述规则继续按上述规则继续(jx)比较。比较。 (2)当当(1)中对应字符均相同时中对应字符均相同时,比较比较s1和和s2的长度的长度: 两者相等时两者相等时,返回返回0； s
18、的长度的长度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+) /逐个字符逐个字符(z f)比较比较 if (s.datait.datai) return 1; if (s.length=t.length) /s=t return 0; else i
19、f (s.lengtht.length) /st第二十五页，共八十三页。4.2.2 4.2.2 串的链式存储及其基本操作实现串的链式存储及其基本操作实现(shxin)(shxin) 也可以采用链式方式存储串也可以采用链式方式存储串,即用单链表形式存储串。这称为即用单链表形式存储串。这称为链链式串式串或或链串链串。 链串中的结点类型定义链串中的结点类型定义: typedef struct snode char data; struct snode *next; LiString;第二十六页，共八十三页。 其中其中data域用来存储组成字符串的字符，域用来存储组成字符串的字符，next域用来指向域
20、用来指向(zh xin)下一个结点。每个字符对应一个结点，一个这样的链表存储一下一个结点。每个字符对应一个结点，一个这样的链表存储一个字符串。下图所示是一个结点大小为个字符串。下图所示是一个结点大小为1的链串。的链串。链串示意图链串示意图第二十七页，共八十三页。 下面讨论在链串上实现串基本运算的算法。下面讨论在链串上实现串基本运算的算法。 （1）StrAssign(s,t) 将一个字符串常量将一个字符串常量(chngling)t赋给串赋给串s,即生成一个其值等于即生成一个其值等于t的串的串s。以下采用尾插法建立链串。以下采用尾插法建立链串。 void StrAssign(LiString *&
21、s,char t) int i; LiString *r,*p;/r始终指向尾结点始终指向尾结点 s=(LiString *)malloc(sizeof(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。以下。以下(yxi)采用尾插法建立复制后的链串采用尾插法建立复制后的链串s。 void StrCopy(LiString *&s,LiSt
22、ring *t) LiString *p=t-next,*q,*r; s=(LiString *)malloc(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) 判断两个判断两个(lin )串是否相等串是否相等:若两个若两个(lin )串串s与与t相等则返回
23、真相等则返回真(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-next; if (p=NULL & q=NULL) return 1; else return 0; 第三十页，共八十三页。（4）StrLength(s)求串长求串长:返回返回(fnhu)串串s中字符个数。中字符个数。 int StrLength(LiString *s) int i=0; LiS
24、tring *p=s-next; while (p!=NULL) i+; p=p-next; return i; 第三十一页，共八十三页。 （5）Concat(s,t) 返回返回(fnhu)由两个串由两个串s和和t连接在一起形成的新串。连接在一起形成的新串。 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=(LiStri
25、ng *)malloc(sizeof(LiString); q-data=p-data; r-next=q;r=q; p=p-next; 第三十二页，共八十三页。 p=t-next; while (p!=NULL) /将将t的所有的所有(suyu)结点复制到结点复制到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)
26、个字符开始的、由连续个字符开始的、由连续(linx)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
27、;kstr 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)个字符中个字符中,即将即将(jjing)s2的第一个字符作为的第一个字符作为s1的第的第i个字符个字符,并返回产生的新串。并返回产生的新串。 LiString *InsStr(LiString *s,int i,Li
28、String *t) int k; LiString *str,*p=s-next,*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=(L
29、iString *)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;q-next=NULL; r-next=q;r=q; p=p-next; r-next=NULL; return str;第三十七页，共八十三页。 （8）DelStr(s,i,j) 从串从串s中删去从第中删去从第i(1iStrLe
30、ngth(s)个字符开始的长度为个字符开始的长度为j的子串的子串,并并返回产生返回产生(chnshng)的新串。的新串。 LiString *DelStr(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;k
31、data=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(LiString); 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个字符构成的子
32、串个字符构成的子串用串用串t替换替换,并返回并返回(fnhu)产生的新串。产生的新串。 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); r=str; if (iStrLength(s) | jStrLength(s) printf(参数不正确参数不正确n); return str; /参数不正确时返回空串参数不正确时返回空串第四十页，共八十三页。 for
33、(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及其后的结点及其后的结点(ji din)复制到复制到str q=(LiString *)malloc(sizeof(LiStr
34、ing); q-data=p-data;q-next=NULL; r-next=q;r=q; p=p-next; r-next=NULL; return str; 第四十二页，共八十三页。 （10）DispStr(s) 输出串输出串s的所有的所有(suyu)元素值。元素值。 void DispStr(LiString *s) LiString *p=s-next; while (p!=NULL) printf(%c,p-data); p=p-next;printf(n); 第四十三页，共八十三页。 例例4.3 在链串中在链串中,设计一个算法设计一个算法(sun f)把最先出现的子串把最先出现的
35、子串ab改为改为xyz。 解解:在串在串s中找到最先出现的子串中找到最先出现的子串ab,p指向指向(zh xin)data域值为域值为a的结点的结点,其后为其后为data域值为域值为b的结点。将它们的的结点。将它们的data域值分别域值分别改为改为x和和z,再创建一个再创建一个data域值为域值为y的结点的结点,将其插入到将其插入到*p之后。之后。本例算法如下本例算法如下:abxzyq修改修改(xigi)pp第四十四页，共八十三页。void Repl(LiString *&s) LiString *p=s-next,*q;int find=0; while (p-next!=NULL & fi
36、nd=0) if (p-data=a & p-next-data=b) p-data=x;p-next-data=z; /替换替换(t hun)为为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相等的子串。通常相等的子串。通常(tngchng)把主串把主串s称为目标串称为目标
37、串,把子串把子串t称为模式串称为模式串,因此定位也称作因此定位也称作模式匹配模式匹配。 模式匹配成功是指在目标串模式匹配成功是指在目标串s中找到一个模式串中找到一个模式串t；不成功则；不成功则指目标串指目标串s中不存在模式串中不存在模式串t。 第四十六页，共八十三页。4.4.1 Brute-Force算法算法 Brute-Force简称为简称为BF算法算法,亦称简单匹配算法亦称简单匹配算法,其基本思路是其基本思路是: 从目标串从目标串s=s0s1sn-1的第一个字符开始和模式串的第一个字符开始和模式串t=t0t1tm-1中的第一个字符比较中的第一个字符比较,若相等若相等,则继续则继续(jx)逐
38、个比较后续字符；否逐个比较后续字符；否则从目标串则从目标串s的第二个字符开始重新与模式串的第二个字符开始重新与模式串t的第一个字符进的第一个字符进行比较。依次类推行比较。依次类推,若从模式串若从模式串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”
39、。BF模式匹模式匹配过程配过程(guchng)如下所示。如下所示。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 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作为作为(zuwi)找到子串的条件。找到子串的条件。第四十八页，共八十三页。int indexpos(SqString str,SqString substr) int i,j,k,idx=-1; for (i=0;istr.length;i+) for (j=
40、i,k=0;str.dataj=substr.datak; j+,k+); if (k=substr.length) /注意注意j每次从每次从i开始开始(kish),有回溯有回溯 return(i); return(-1);算法算法(sun f)1第四十九页，共八十三页。 可以可以(ky)少一个扫描变量。少一个扫描变量。例如例如,设目标串设目标串s=“cddcdc”,模式串模式串t=“cdc”。BF模式匹配过程如下所示。模式匹配过程如下所示。第五十页，共八十三页。int index(SqString s,SqString t) int i=0,j=0; while (is.length & j
41、=t.length) return(i-t.length); /返回匹配的第一个字符的下标返回匹配的第一个字符的下标(xi bio) else return -1; /模式匹配不成功模式匹配不成功 算法算法(sun f)2第五十一页，共八十三页。 这个算法简单这个算法简单,易于易于(yy)理解理解,但效率不高但效率不高,主要原因是主要原因是:主串指主串指针针i在若干个字符序列比较相等后在若干个字符序列比较相等后,若有一个字符比较不相等若有一个字符比较不相等,仍需仍需回溯回溯（即（即i=i-j+1）。）。 该算法在最好情况下的时间复杂度为该算法在最好情况下的时间复杂度为O(m),即主串的前即主串
42、的前m个字符个字符正好等于模式串的正好等于模式串的m个字符。在最坏情况下的时间复杂度为个字符。在最坏情况下的时间复杂度为O(n*m)。 第五十二页，共八十三页。 4.3.2 KMP算法算法 KMP算法是算法是D.E.Knuth、J.H.Morris和和V.R.Pratt共同提出的共同提出的,简简称称KMP算法。该算法较算法。该算法较BF算法有较大改进算法有较大改进,主要是消除了主串指主要是消除了主串指针的回溯针的回溯(hu s),从而使算法效率有了某种程度的提高。从而使算法效率有了某种程度的提高。 第五十三页，共八十三页。Donald Knuth（1938年），算法和程序设计技年），算法和程序
43、设计技术的先驱者，计算机排版系统术的先驱者，计算机排版系统TEX和和METAFONT的发明者，他因这些成就和大量创的发明者，他因这些成就和大量创造性的影响深远的著作（造性的影响深远的著作（19部书和部书和160篇论文）篇论文）而誉满全球。作为斯坦福大学计算机程序设计艺而誉满全球。作为斯坦福大学计算机程序设计艺术术(ysh)的荣誉退休教授，的荣誉退休教授，他当前正全神贯注于完他当前正全神贯注于完成其关于计算机科学的史诗性的七卷集。这一成其关于计算机科学的史诗性的七卷集。这一伟大工程在伟大工程在1962年他还是加利福尼亚理工学院年他还是加利福尼亚理工学院的研究生时就开始了的研究生时就开始了。他于。
44、他于1974年获得计算机科年获得计算机科学界最高奖图灵奖。学界最高奖图灵奖。第五十四页，共八十三页。 第第 1 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=3，j=2 开始开始 t=a a a b 第五十五页，共八十三页。s=abcabababcdet=ababcj01234tjababcNextj-10012t t中中”b”b” ”a a”, ,而而s s中中”b”b”=t=t中中”b”b”, ,故不必故不必(bb)(bb)从从s1s1开始开始s=abcababa
45、bcdet=ababc不相等不相等(xingdng)(xingdng),s,s后后移移s=abcabababcdet=ababc没有没有(mi yu)(mi yu)必要从必要从s4s4开始开始s=abcabababcdet=ababc成功成功第五十六页，共八十三页。 所谓所谓真子串真子串是指模式是指模式(msh)串串t存在某个存在某个k(0kj)，使得，使得t0t1tk = tj-ktj-k+1tj 成立。成立。 例如，例如，t= abab, 即即t0t1t2t3 也就是说，也就是说， “ab”是是真子串真子串。 真子串真子串就是模式串中隐藏的信息，利用它来提高模式匹配的效率。就是模式串中隐藏
46、的信息，利用它来提高模式匹配的效率。不同于前面不同于前面(qin mian)的子真串的定义的子真串的定义第五十七页，共八十三页。 一般一般(ybn)情况情况:设主串设主串s=s0s1sn-1,模式模式t=t0t1tm-1,在进行第在进行第i趟匹配时，出现以下情况：趟匹配时，出现以下情况：这时，应有这时，应有t0t1tj-1=si-jsi-j+1si-1 (4.1)如果在模式如果在模式t中，中，t0t1tj-1t1t2tj(4.2) s： s0 s1 si-j si-j+1 si-1 si si+1 sn-1 t： t0 t1 tj-1 tj tj+1 sm-1 第五十八页，共八十三页。 则回溯
47、到则回溯到si-j+1开始与开始与t匹配，必然匹配，必然“失配失配”，理由很简单：由，理由很简单：由(4.1)式和式和(4.2)式综合可知：式综合可知：t0t1tj-1si-j+1si-j+2si 既然如此，回溯到既然如此，回溯到si-j+1开始与开始与t匹配可以不做。那么，回溯到匹配可以不做。那么，回溯到si-j+2开开始与始与t匹配又怎么样？从上面匹配又怎么样？从上面(shng min)推理可知，如果推理可知，如果: t0t1tj-2t2t3tj仍然有仍然有 t0t1tj-2si-j+2si-j+3si第五十九页，共八十三页。 这样的比较仍然这样的比较仍然(rngrn)“失配失配”。依此类
48、推，直到对于某一个。依此类推，直到对于某一个值值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趟比较趟比较“失配失配”时的模式时的模式(msh)t从当前位置直接右滑从当前位置直接右滑j-k位。而位。而这里的这里的k即为即为nextj。 s： s0 s1 si-j si-j+1 si-k si-k+1 si-
49、1 si si+1 sn-1 t： t0 t1 tk-1 tk tj-1 tj tj+1 sm-1 s： s0 s1 si-j si-j+1 si-k si-k+1 si-1 si si+1 sn-1 t： t0 t1 tk-1 tk tj-1 tj tj+1 sm-1 t 右滑右滑 j-k 位位 第六十一页，共八十三页。 例如例如(lr)t=abab,由于由于t0t1 =t2t3(这里这里k=1,j=3),则存在真子串。则存在真子串。设设s=abacabab,t=abab,第一次匹配过程如下所示。第一次匹配过程如下所示。 此时不必从此时不必从i=1(i=i-j+1=1),j=0重新开始重新开
50、始(kish)第二次匹配。因第二次匹配。因t0t1,s1=t1,必有必有s1t0,又因又因t0 =t2,s2=t2,所以必有所以必有s2=t0。因此。因此,第二次匹第二次匹配可直接从配可直接从i=3,j=1开始。开始。 第六十二页，共八十三页。 为此为此,定义定义nextj函数（函数（失配函数失配函数）如下）如下: maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1” 当此集合当此集合(jh)非空时非空时 -1 当当j=0时时 0 其他情况其他情况nextj=j0123tjababnextj-1001t=“abab”t=“abab”对应对应(duyng)(duyng)的