《c语言字符串数组和特殊矩阵.pptx》由会员分享，可在线阅读，更多相关《c语言字符串数组和特殊矩阵.pptx（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 4.1 字符串字符串 4.1.1 字符串的基本概念字符串的基本概念 字符串是由零个或多个字符构成的有限序字符串是由零个或多个字符构成的有限序字符串是由零个或多个字符构成的有限序字符串是由零个或多个字符构成的有限序列，一般可表示成如下形式：列，一般可表示成如下形式：列，一般可表示成如下形式：列，一般可表示成如下形式：“c c1 1 c c2 2 c c3 n”(n”(n0)0)串中所含字符的个数串中所含字符的个数串中所含字符的个数串中所含字符的个数n n称为字符串的长度；当称为字符串的长度；当称为字符串的长度；当称为字符串的长度；当n=0n=0时，称字符串为时，称字符串为时，称字符串为时，称字
2、符串为空串空串空串空串。串中任意个连续的字符构成的子序列称为该串中任意个连续的字符构成的子序列称为该串中任意个连续的字符构成的子序列称为该串中任意个连续的字符构成的子序列称为该串的串的串的串的子串子串子串子串，包含子串的串称，包含子串的串称，包含子串的串称，包含子串的串称为为为为主串主串主串主串。通常称字符。通常称字符。通常称字符。通常称字符在字符串序列中的序号为该字符在串中的位置。在字符串序列中的序号为该字符在串中的位置。在字符串序列中的序号为该字符在串中的位置。在字符串序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串子串在主串中的位置以子串的第一个字符在主串子串
3、在主串中的位置以子串的第一个字符在主串子串在主串中的位置以子串的第一个字符在主串中的位置来表示。例如：中的位置来表示。例如：中的位置来表示。例如：中的位置来表示。例如：T=“STUDENT”T=“STUDENT”，S=“UDEN”,S=“UDEN”,则则则则S S是是是是T T的子串，的子串，的子串，的子串，S S在在在在T T中出现的位中出现的位中出现的位中出现的位置为置为置为置为3 3。第1页/共65页 两个两个两个两个字符串相等字符串相等字符串相等字符串相等，当且仅当两个串的长度相，当且仅当两个串的长度相，当且仅当两个串的长度相，当且仅当两个串的长度相等，并且各个对应位置的字符都相等。例
4、如：等，并且各个对应位置的字符都相等。例如：等，并且各个对应位置的字符都相等。例如：等，并且各个对应位置的字符都相等。例如：T1=T1=T1=T1=“REDROSEREDROSEREDROSEREDROSE”T2=T2=T2=T2=“RED ROSERED ROSERED ROSERED ROSE”由于由于由于由于T1T1T1T1和和和和T2T2T2T2的长度不相等，因此的长度不相等，因此的长度不相等，因此的长度不相等，因此T1T2T1T2T1T2T1T2。若若若若 T3=T3=T3=T3=“STUDENTSTUDENTSTUDENTSTUDENT”T4=T4=T4=T4=“STUDENSST
5、UDENSSTUDENSSTUDENS”虽然虽然虽然虽然T3T3T3T3和和和和T4T4T4T4的长度相等，但两者有些对应的字符的长度相等，但两者有些对应的字符的长度相等，但两者有些对应的字符的长度相等，但两者有些对应的字符不同，因而不同，因而不同，因而不同，因而T3T4T3T4T3T4T3T4。值得一提的是，若值得一提的是，若值得一提的是，若值得一提的是，若S=S=S=S=“”，此时，此时，此时，此时S S S S由一个由一个由一个由一个空格字符组成，其长度为空格字符组成，其长度为空格字符组成，其长度为空格字符组成，其长度为1 1 1 1，它不等价于空串，它不等价于空串，它不等价于空串，它不
6、等价于空串，因为空串的长度为因为空串的长度为因为空串的长度为因为空串的长度为0 0 0 0。第2页/共65页4.1.2 字符串类的定义字符串类的定义ADT string ADT string ADT string ADT string 数据对象数据对象数据对象数据对象D D D D：由零个或多个：由零个或多个：由零个或多个：由零个或多个字符型字符型字符型字符型的数据元素的数据元素的数据元素的数据元素构成的有限集合；构成的有限集合；构成的有限集合；构成的有限集合；数据关系数据关系数据关系数据关系R R R R：aaa|其中其中其中其中a a a ai i i i,a,a,a,ai+1i+1i+1
7、i+1 D,D,D,D,i=1,2,i=1,2,i=1,2,i=1,2,n-1 n-1 n-1 n-1 字符串的基本操作如下：字符串的基本操作如下：字符串的基本操作如下：字符串的基本操作如下：（1 1 1 1）Strcreate(S)Strcreate(S)Strcreate(S)Strcreate(S)（2 2 2 2）Strassign(S,T)Strassign(S,T)Strassign(S,T)Strassign(S,T)（3 3）Strlength(S)Strlength(S)（4 4）Strempty(S)Strempty(S)第3页/共65页 （5 5）Strclear(S)S
8、trclear(S)（6 6 6 6）Strcompare(SStrcompare(SStrcompare(SStrcompare(S1 1 1 1，S S S S2 2 2 2)（7 7）Strconcat(SStrconcat(S1 1，S S2 2)（8 8）Substring(S,i,len)Substring(S,i,len)（9 9）Index(P,T)Index(P,T)（1010）Strinsert(S,i,T)Strinsert(S,i,T)（1111）Strdelete(S,i,len)Strdelete(S,i,len)（1212）Replace(S,TReplace(S
9、,T1 1,T,T2 2)（1313）Strdestroy(S)Strdestroy(S)ADT string ADT string 第4页/共65页4.1.3 4.1.3 字符串的存储及其实现字符串的存储及其实现 1 1 1 1、串的顺序存储及其部分运算的实现、串的顺序存储及其部分运算的实现、串的顺序存储及其部分运算的实现、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放，具体类型定义如下：串的顺序存储使用数组存放，具体类型定义如下：串的顺序存储使用数组存放，具体类型定义如下：串的顺序存储使用数组存放，具体类型定义如下：#define MAXSIZE 100#define MAXSIZ
10、E 100#define MAXSIZE 100#define MAXSIZE 100 typedef struct typedef struct typedef struct typedef struct char strMAXSIZE;char strMAXSIZE;char strMAXSIZE;char strMAXSIZE;int length;int length;int length;int length;seqstring;seqstring;seqstring;seqstring;第5页/共65页（1 1 1 1）插入运算）插入运算）插入运算）插入运算strinsert(S,
11、i,T)strinsert(S,i,T)strinsert(S,i,T)strinsert(S,i,T)void strinsert(seqstring*S,int i,seqstring T)void strinsert(seqstring*S,int i,seqstring T)int k;int k;if(iS-length+1|S-length+if(iS-length+1|S-length+T.lengthMAXSIZE)T.lengthMAXSIZE)printf(connot insertn“);printf(connot insertn“);else else for(k=S-
12、length-1;k=i-1;k-)for(k=S-length-1;k=i-1;k-)S-strT.length+k=S-strk;S-strT.length+k=S-strk;for(k=0;kT.length;k+)for(k=0;kstri-1+k=T.strk;S-stri-1+k=T.strk;S-length=S-length+T.length;S-length=S-length+T.length;S-strS-length=0;S-strS-length=0;第6页/共65页（2 2 2 2）删除运算）删除运算）删除运算）删除运算strdelete(S,i,len)strdel
13、ete(S,i,len)strdelete(S,i,len)strdelete(S,i,len)void strdelete(seqstring*S,int i,int void strdelete(seqstring*S,int i,int void strdelete(seqstring*S,int i,int void strdelete(seqstring*S,int i,int len)len)len)len)int k;int k;int k;int k;if(iS-length|i+len-1S-if(iS-length|i+len-1S-if(iS-length|i+len-1
14、S-if(iS-length|i+len-1S-length)length)length)length)printf(printf(printf(printf(“cannot deleten cannot deleten cannot deleten cannot deleten”););););else else else else for(k=i-1+len;kS-for(k=i-1+len;kS-for(k=i-1+len;kS-for(k=i-1+len;klength;k+)length;k+)length;k+)length;k+)S-strk-len=S-strk;S-strk-
15、len=S-strk;S-strk-len=S-strk;S-strk-len=S-strk;S-length=S-length-len;S-length=S-length-len;S-length=S-length-len;S-length=S-length-len;S-strS-length=S-strS-length=S-strS-length=S-strS-length=0000;第7页/共65页（3 3 3 3）连接运算）连接运算）连接运算）连接运算strconcat(Sstrconcat(Sstrconcat(Sstrconcat(S1 1 1 1,S,S,S,S2 2 2 2)s
16、eqstring*strconcat(seqstring S1,seqstring seqstring*strconcat(seqstring S1,seqstring S2)S2)int i;seqstring*r;int i;seqstring*r;if (S1.length+S2.lengthMAXSIZE)if (S1.length+S2.lengthMAXSIZE)printf(cannot concate);printf(cannot concate);return(NULL);return(NULL);else else r=(seqstring*)malloc r=(seqst
17、ring*)malloc(sizeof(seqstring);(sizeof(seqstring);for(i=0;istri=for(i=0;istri=S1.stri;S1.stri;for(i=0;iS2.length;i+)for(i=0;istr S1.length+i=S2.stri;r-str S1.length+i=S2.stri;r-length=S1.length+S2.length;r-length=S1.length+S2.length;r-strr-length=0;r-strr-length=0;return(r);return(r);第8页/共65页（4 4 4
18、4）求子串运算）求子串运算）求子串运算）求子串运算substring(S,i,len)substring(S,i,len)substring(S,i,len)substring(S,i,len)seqstring*substring(seqstring S,int i,int len)seqstring*substring(seqstring S,int i,int len)int k;seqstring*r;int k;seqstring*r;if(iS.length|i+len-1S.length)if(iS.length|i+len-1S.length)printf(“errorn”);
19、return(NULL);printf(“errorn”);return(NULL);else else r=(seqstring*)malloc r=(seqstring*)malloc(sizeof(seqstring);(sizeof(seqstring);for(k=0;kstrk=for(k=0;kstrk=S.stri-1+k;S.stri-1+k;r-length=len;r-length=len;r-strr-length=0;r-strr-length=0;return(r);return(r);第9页/共65页2 2 2 2 串的链接存储及其部分运算的实现串的链接存储及其部
20、分运算的实现串的链接存储及其部分运算的实现串的链接存储及其部分运算的实现 串的链接存储采用单链表的形式实现，其中每串的链接存储采用单链表的形式实现，其中每串的链接存储采用单链表的形式实现，其中每串的链接存储采用单链表的形式实现，其中每个结点的定义如下：个结点的定义如下：个结点的定义如下：个结点的定义如下：typedef struct nodetypedef struct nodetypedef struct nodetypedef struct node char data;char data;char data;char data;struct node*next;struct node*n
21、ext;struct node*next;struct node*next;linkstrnode;linkstrnode;linkstrnode;linkstrnode;typedef linkstrnode*linkstring;typedef linkstrnode*linkstring;typedef linkstrnode*linkstring;typedef linkstrnode*linkstring;例如，串例如，串例如，串例如，串S=S=S=S=“abcdeabcdeabcdeabcde”，其链接存储结构如下图所，其链接存储结构如下图所，其链接存储结构如下图所，其链接存储结构
22、如下图所示：示：示：示：a ab bc cd de e S S第10页/共65页（1 1 1 1）创建字符串运算）创建字符串运算）创建字符串运算）创建字符串运算strcreate(S)strcreate(S)strcreate(S)strcreate(S)void strcreate(linkstring*S)void strcreate(linkstring*S)void strcreate(linkstring*S)void strcreate(linkstring*S)char ch;linkstrnode*p,*r;char ch;linkstrnode*p,*r;char ch;li
23、nkstrnode*p,*r;char ch;linkstrnode*p,*r;*S=NULL;r=NULL;*S=NULL;r=NULL;*S=NULL;r=NULL;*S=NULL;r=NULL;while(ch=getchar()!=while(ch=getchar()!=while(ch=getchar()!=while(ch=getchar()!=nnnn)p=(linkstrnode p=(linkstrnode p=(linkstrnode p=(linkstrnode*)malloc(sizeof(linkstrnode);*)malloc(sizeof(linkstrnode
24、);*)malloc(sizeof(linkstrnode);*)malloc(sizeof(linkstrnode);p-data=ch;p-data=ch;p-data=ch;p-data=ch;if(*S=NULL)*S=p;if(*S=NULL)*S=p;if(*S=NULL)*S=p;if(*S=NULL)*S=p;else r-next=p;else r-next=p;else r-next=p;else r-next=p;r=p;/*r r=p;/*r r=p;/*r r=p;/*r移向当前链接串的最后一个字符的位移向当前链接串的最后一个字符的位移向当前链接串的最后一个字符的位移
25、向当前链接串的最后一个字符的位置置置置*/if(r!=NULL)r-next=NULL;/*if(r!=NULL)r-next=NULL;/*if(r!=NULL)r-next=NULL;/*if(r!=NULL)r-next=NULL;/*处理表尾结点指处理表尾结点指处理表尾结点指处理表尾结点指针域针域针域针域*/第11页/共65页（2 2 2 2）插入运算）插入运算）插入运算）插入运算strinsert(S,i,T)strinsert(S,i,T)strinsert(S,i,T)strinsert(S,i,T)void strinsert(linkstring*S,int i,linkst
26、ring T)void strinsert(linkstring*S,int i,linkstring T)int k;linkstring p,q;int k;linkstring p,q;p=*S,k=1;p=*S,k=1;while(p&ki-1)while(p&knext;k+;p=p-next;k+;if(!p)printf(errorn);if(!p)printf(errorn);else else q=T;q=T;while(q-next)q=q-next;while(q-next)q=q-next;q-next=p-next;p-next=T;q-next=p-next;p-n
27、ext=T;第12页/共65页（3 3 3 3）删除运算）删除运算）删除运算）删除运算strdelete(S,i,len)strdelete(S,i,len)strdelete(S,i,len)strdelete(S,i,len)void strdelete(linkstring*S,int i,int len)void strdelete(linkstring*S,int i,int len)void strdelete(linkstring*S,int i,int len)void strdelete(linkstring*S,int i,int len)int k;linkstring
28、p,q,r;int k;linkstring p,q,r;int k;linkstring p,q,r;int k;linkstring p,q,r;p=*S,q=null;k=1;p=*S,q=null;k=1;p=*S,q=null;k=1;p=*S,q=null;k=1;/*/*/*/*用用用用p p p p查找查找查找查找S S S S的第的第的第的第i i i i个元素，个元素，个元素，个元素，q q q q始终跟踪始终跟踪始终跟踪始终跟踪p p p p的前驱的前驱的前驱的前驱*/while(p&ki)while(p&ki)while(p&ki)while(p&knext;k+;q=
29、p;p=p-next;k+;q=p;p=p-next;k+;q=p;p=p-next;k+;if(!p)printf(error1n);if(!p)printf(error1n);if(!p)printf(error1n);if(!p)printf(error1n);else else else else k=1;k=1;k=1;k=1;/*p /*p /*p /*p从第从第从第从第i i i i个元素开始查找长度为个元素开始查找长度为个元素开始查找长度为个元素开始查找长度为lenlenlenlen子串的最后元子串的最后元子串的最后元子串的最后元素素素素*/while(klen&p)while
30、(klen&p)while(klen&p)while(knext;k+;p=p-next;k+;p=p-next;k+;p=p-next;k+;if(!p)printf(error2n);if(!p)printf(error2n);if(!p)printf(error2n);if(!p)printf(error2n);第13页/共65页 else else else else if(!q)r=*S;*S=p-next;if(!q)r=*S;*S=p-next;if(!q)r=*S;*S=p-next;if(!q)r=*S;*S=p-next;/*/*/*/*被删除的子串位于被删除的子串位于被删
31、除的子串位于被删除的子串位于S S S S的最前面的最前面的最前面的最前面*/else else else else /*/*/*/*被删除的子串位于的中间或最后被删除的子串位于的中间或最后被删除的子串位于的中间或最后被删除的子串位于的中间或最后*/r=q-next;q-next=p-next;r=q-next;q-next=p-next;r=q-next;q-next=p-next;r=q-next;q-next=p-next;p-next=null;p-next=null;p-next=null;p-next=null;while(r!=null)while(r!=null)while(r
32、!=null)while(r!=null)p=r;r=r-next;free(p);p=r;r=r-next;free(p);p=r;r=r-next;free(p);p=r;r=r-next;free(p);第14页/共65页（4 4 4 4）连接运算）连接运算）连接运算）连接运算strconcat(Sstrconcat(Sstrconcat(Sstrconcat(S1 1 1 1,S,S,S,S2 2 2 2)void strconcat(linkstring*S1,linkstring S2)void strconcat(linkstring*S1,linkstring S2)void
33、strconcat(linkstring*S1,linkstring S2)void strconcat(linkstring*S1,linkstring S2)linkstring p;linkstring p;linkstring p;linkstring p;if(!(*S1)*S1=S2;return;if(!(*S1)*S1=S2;return;if(!(*S1)*S1=S2;return;if(!(*S1)*S1=S2;return;else else else else if(S2)/*S1 if(S2)/*S1 if(S2)/*S1 if(S2)/*S1和和和和S2S2S2S2
34、均不为空串的情形均不为空串的情形均不为空串的情形均不为空串的情形*/p=*S1;/*p=*S1;/*p=*S1;/*p=*S1;/*用用用用p p p p查找查找查找查找S1S1S1S1的最后一个字符的位的最后一个字符的位的最后一个字符的位的最后一个字符的位置置置置*/while(p-next)p=p-next;while(p-next)p=p-next;while(p-next)p=p-next;while(p-next)p=p-next;p-next=S2;/*p-next=S2;/*p-next=S2;/*p-next=S2;/*将串将串将串将串S2S2S2S2连接到连接到连接到连接到S
35、1S1S1S1之后之后之后之后*/第15页/共65页（5 5 5 5）求子串运算）求子串运算）求子串运算）求子串运算substring(S,i,len)substring(S,i,len)substring(S,i,len)substring(S,i,len)linkstring substring(linkstring S,int i,int linkstring substring(linkstring S,int i,int linkstring substring(linkstring S,int i,int linkstring substring(linkstring S,int
36、i,int len)len)len)len)int k;linkstring p,q,r,t;int k;linkstring p,q,r,t;int k;linkstring p,q,r,t;int k;linkstring p,q,r,t;p=S,k=1;p=S,k=1;p=S,k=1;p=S,k=1;/*/*/*/*用用用用p p p p查找查找查找查找S S S S中的第中的第中的第中的第i i i i个字符个字符个字符个字符*/while(p&knext;k+;while(p&knext;k+;while(p&knext;k+;while(p&knext;k+;if(!p)print
37、f(error1n);if(!p)printf(error1n);if(!p)printf(error1n);if(!p)printf(error1n);return(null);return(null);return(null);return(null);else else else else r=(linkstring)malloc r=(linkstring)malloc r=(linkstring)malloc r=(linkstring)malloc(sizeof(linkstrnode);(sizeof(linkstrnode);(sizeof(linkstrnode);(size
38、of(linkstrnode);r-data=p-data;r-next=null;r-data=p-data;r-next=null;r-data=p-data;r-next=null;r-data=p-data;r-next=null;第16页/共65页 k=1;q=r;/*k=1;q=r;/*k=1;q=r;/*k=1;q=r;/*用用用用q q q q始终指向子串的最后一个字符的始终指向子串的最后一个字符的始终指向子串的最后一个字符的始终指向子串的最后一个字符的位置位置位置位置*/while(p-next&knext&knext&knext&knext;k+;p=p-next;k+;p
39、=p-next;k+;p=p-next;k+;t=(linkstring)malloc(sizeof t=(linkstring)malloc(sizeof t=(linkstring)malloc(sizeof t=(linkstring)malloc(sizeof(linkstrnode);(linkstrnode);(linkstrnode);(linkstrnode);t-data=p-data;t-data=p-data;t-data=p-data;t-data=p-data;q-next=t;q=t;q-next=t;q=t;q-next=t;q=t;q-next=t;q=t;if
40、(klen)printf(error2n);if(klen)printf(error2n);if(klen)printf(error2n);if(knext=null;return(r);/*q-next=null;return(r);/*q-next=null;return(r);/*q-next=null;return(r);/*处理子串的尾处理子串的尾处理子串的尾处理子串的尾部部部部*/第17页/共65页 4.2 4.2 字符串的模式匹配字符串的模式匹配 寻找字符串寻找字符串寻找字符串寻找字符串p p p p在字符串在字符串在字符串在字符串t t t t中首次出现的起始位置中首次出现的起
41、始位置中首次出现的起始位置中首次出现的起始位置称为字符串的称为字符串的称为字符串的称为字符串的模式匹配模式匹配模式匹配模式匹配，其中称，其中称，其中称，其中称p p p p为为为为模式模式模式模式(patternpatternpatternpattern），），），），t t t t为为为为正文正文正文正文(text)(text)(text)(text)，t t t t的长度远远大于的长度远远大于的长度远远大于的长度远远大于p p p p的长度。的长度。的长度。的长度。4.2.1 4.2.1 朴素的模式匹配算法朴素的模式匹配算法 朴素模式匹配算法的基本思想是：用朴素模式匹配算法的基本思想是：用
42、朴素模式匹配算法的基本思想是：用朴素模式匹配算法的基本思想是：用p p p p中的每中的每中的每中的每个字符去与个字符去与个字符去与个字符去与t t t t中的字符一一比较：中的字符一一比较：中的字符一一比较：中的字符一一比较：正文正文正文正文t t t t：t t t t1 1 1 1 t t t t2 2 2 2 t t t tm m m mt t t tn n n n 模式模式模式模式p p p p：p p p p1 1 1 1 p p p p2 2 2 2 p p p pm m m m如果如果如果如果t t t t1 1 1 1=p=p=p=p1 1 1 1,t,t,t,t2 2 2
43、2=p=p=p=p2 2 2 2,.t.t.t.tm m m m=p=p=p=pm m m m，则模式匹配成功；，则模式匹配成功；，则模式匹配成功；，则模式匹配成功；否则否则否则否则 第18页/共65页将将将将p p p p向右移动一个字符的位置，重新用向右移动一个字符的位置，重新用向右移动一个字符的位置，重新用向右移动一个字符的位置，重新用p p p p中的字符中的字符中的字符中的字符从头开始与从头开始与从头开始与从头开始与t t t t中相对应的字符依次比较，即：中相对应的字符依次比较，即：中相对应的字符依次比较，即：中相对应的字符依次比较，即：t t t t1 1 1 1 t t t t
44、2 2 2 2 t t t t3 3 3 3 t t t tm m m m t t t tm+1m+1m+1m+1t t t tn n n n p p p p1 1 1 1 p p p p2 2 2 2 p p p pm-1 m-1 m-1 m-1 p p p pm m m m 如此反复，直到匹配成功或者如此反复，直到匹配成功或者如此反复，直到匹配成功或者如此反复，直到匹配成功或者p p p p已经移到使已经移到使已经移到使已经移到使t t t t中剩中剩中剩中剩下的字符个数小于下的字符个数小于下的字符个数小于下的字符个数小于p p p p的长度的位置，此时意味着的长度的位置，此时意味着的长度
45、的位置，此时意味着的长度的位置，此时意味着模式匹配失败，表示模式匹配失败，表示模式匹配失败，表示模式匹配失败，表示t t t t中没有子串与模式中没有子串与模式中没有子串与模式中没有子串与模式p p p p相等，相等，相等，相等，我们约定返回我们约定返回我们约定返回我们约定返回-1-1-1-1代表匹配失败。代表匹配失败。代表匹配失败。代表匹配失败。朴素模式匹配算法的具体实现如下：朴素模式匹配算法的具体实现如下：朴素模式匹配算法的具体实现如下：朴素模式匹配算法的具体实现如下：第19页/共65页int index(seqstring p,seqstring t)int index(seqstrin
46、g p,seqstring t)int index(seqstring p,seqstring t)int index(seqstring p,seqstring t)int i,j,succ;int i,j,succ;int i,j,succ;int i,j,succ;i=0;succ=0;/*succ i=0;succ=0;/*succ i=0;succ=0;/*succ i=0;succ=0;/*succ为匹配成功的标志为匹配成功的标志为匹配成功的标志为匹配成功的标志*/while(it.length-p.length+1)&while(it.length-p.length+1)&whi
47、le(it.length-p.length+1)&while(it.length-p.length+1)&(!succ)(!succ)(!succ)(!succ)j=0;succ=1;/*j=0;succ=1;/*j=0;succ=1;/*j=0;succ=1;/*用用用用j j j j扫描模式扫描模式扫描模式扫描模式p*/p*/p*/p*/while(j=p.length-1)&while(j=p.length-1)&while(j=p.length-1)&while(j=p.length-1)&succ)succ)succ)succ)if(p.strj=t.stri+j)if(p.strj
48、=t.stri+j)if(p.strj=t.stri+j)if(p.strj=t.stri+j)j+;j+;j+;j+;else succ=0;else succ=0;else succ=0;else succ=0;+i;+i;+i;+i;if(succ)return(i-1);if(succ)return(i-1);if(succ)return(i-1);if(succ)return(i-1);else return(-1);else return(-1);else return(-1);else return(-1);第20页/共65页4.2.2 4.2.2 快速模式匹配算法（快速模式匹配
49、算法（KMPKMP算法）算法）首先我们来分析下图所示的情况：首先我们来分析下图所示的情况：首先我们来分析下图所示的情况：首先我们来分析下图所示的情况：t t t t0 0 0 0 t t t t1 1 1 1 t t t t2 2 2 2 t t t tk k k k t t t tk+1k+1k+1k+1 t t t tk+2k+2k+2k+2t t t tr-2r-2r-2r-2 t t t tr-1r-1r-1r-1 t t t tr r r r.p p p p0 0 0 0 p p p p1 1 1 1 p p p p2 2 2 2 p p p pi-2i-2i-2i-2 p p p
50、pi-1i-1i-1i-1 p p p pi i i i.（4-14-14-14-1）t t t t0 0 0 0 t t t t1 1 1 1 t t t t2 2 2 2 t t t tk k k k t t t tk+1k+1k+1k+1 t t t tk+2k+2k+2k+2t t t tr-2r-2r-2r-2 t t t tr-1r-1r-1r-1 t t t tr r r r.p p p p0 0 0 0 p p p p1 1 1 1 p p p pi-2i-2i-2i-2 p p p pi-1i-1i-1i-1 p p p pi i i i （4-24-24-24-2）t t0