知识点串的模式匹配课件.ppt

1、o子串定位运算又称为模式匹配或串匹配，此运算的应子串定位运算又称为模式匹配或串匹配，此运算的应用非常广泛。例如，文本编辑程序中，经常要查找某用非常广泛。例如，文本编辑程序中，经常要查找某一特定单词出现的位置。解此问题的有效算法能极大一特定单词出现的位置。解此问题的有效算法能极大地提高文本编辑程序的响应性能。地提高文本编辑程序的响应性能。串的模式匹配定义串的模式匹配定义:在主串中寻找子串在串中的位置。在主串中寻找子串在串中的位置。在模式匹配中，子串称为在模式匹配中，子串称为模式串模式串，主，主串称为串称为目标串目标串。o4.3 串的模式匹配算法串的模式匹配算法(知识点三知识点三)o4.3.1 求

2、子串位置的定位函数求子串位置的定位函数 例如：对某文本进行编辑时，可以运用如下步骤：（1）编辑；（2）查找“输入查找文本（字符串）”；（3）找出对应 的串 AbcdefghijklmnopqrstuvwT串pos=4 defghijkS串按照上述主串按照上述主串S和子串和子串T求子串位置的定位函数求子串位置的定位函数 int Index(SString S,SString T,int pos)/返回子串返回子串T在主串在主串S中第中第pos个字符之后的位置。若不存在，个字符之后的位置。若不存在，/则函数值为则函数值为0。其中，。其中，T非空，非空，1posStrLength(S)。i=pos;

3、j=1;while(i=S0&j T0)return i-T0;else return 0;/Index p79算法4.5主串主串s=ababcabcacbab，模式，模式T=abcac bi=11J=6主串主串s 模式串T=abcac 模式串T=abcac 模式串T=abcac i=6if(Si=Tj)+i;+j;/继续比较后继字符继续比较后继字符 else i=i-j+2;j=1;核心语句核心语句返回值为11-5=6因为T0=5 算法算法4.5 特点一：特点一：特点二：特点二：特点特点 三：三：算法算法4.5 因为一种有回溯的模式匹配算法一种有回溯的模式匹配算法;所以，在最坏情况下的时间复

4、杂度是所以，在最坏情况下的时间复杂度是O(n*m)。o4.3.2 又称又称 KMP模式匹配算法。模式匹配算法。KMP算法优点：算法优点：可以在可以在O(M+N)的时间复杂度内完成模式匹配操作，即的时间复杂度内完成模式匹配操作，即对对模式匹配算法的改进，取消了主串的回溯模式匹配算法的改进，取消了主串的回溯。KMP算法基本思想算法基本思想：每当匹配过程中出现字符比较每当匹配过程中出现字符比较不等时，不等时，i不回溯。不回溯。i=3，j=3时，失败时，失败即即s3 t3 ；;S1=t1 ;s2=t2;因为因为t1t2;所以所以t1s2a b a b c a b c a c b a bija b c

5、a c a b a b c a b c a c b a ba b c a c a b a b c a b c a c b a ba b c a c iji=7，j=5失败失败s4=t2;t1t2t1s4a b a b c a b c a c b a ba b c a c a b a b c a b c a c b a ba b c a c iji=7，j=5失败失败s5=t3;t1t3t1s5a b a b c a b c a c b a ba b c a c a b a b c a b c a c b a ba b c a c iji=7，j=5失败失败s5=t3;t1t3t1s5匹配成功匹

6、配成功a b a b c a b c a c b a ba b c a c 两式联立可得：两式联立可得：ijSi-（k1）.si-1P1-pk-1Pj-(k-1)Pj-1当 si pj失匹时ijik 两式联立可得：两式联立可得：相等，因此，匹配仅需从从第从第1位往右位往右经过经过k-1位位从从j-1位往左位往左经过经过k-1位位目前需要解决的问题是目前需要解决的问题是（1）若）若i不需回溯，则不需回溯，则 j应该退回到何处？应该退回到何处？（2）设退回到）设退回到 nextj，则则nextj=？（3）对于给定的模式串，如何求解）对于给定的模式串，如何求解nextj是问题是问题的关键。的关键。（

7、4）nextj与与s串无关，只与串无关，只与t串有关串有关0 当当 j=1max k|1 k j 且且 “p1p2 pk 1 =“pj k+1 pj k+2 pj 1 (相同的前缀子串与后缀子串的最大长度相同的前缀子串与后缀子串的最大长度+1)1 其他其他 Next j=Next j 函数定义和计算模式如下：例例:o设有模式串设有模式串T=“abaabcac“,计算计算nextj j 1 2 3 4 5 6 7 8模式串模式串 a b a a b c a c nextj 0 1 1 2 2 3 1 2 int Index_KMP(SString S,SString T,int pos)/1po

8、sStrLength(S)i=pos;j=1;while(i=S0&j T0)return i-T0;/匹配成功 else return 0;/Index_KMP算法4.6 P82主串S=“acabaabaabcacaabc”模式串T=“abaabc”begin(j T0)?endreturn i-T0i=S0&j=T0)?yi=pos;j=1;(j=0|Si=Tj)?yi=i+1 ;j=j+1;NNj=nextjNy返返回回0算法是在已知模式串的算法是在已知模式串的nextnext函数值的基础上执行函数值的基础上执行的，那么，如何求得模式串的的，那么，如何求得模式串的nextnext函数值呢

9、？函数值呢？从上述讨从上述讨论可见：论可见：此函数值仅取决于模式串本身而和相匹配的主串无关。此函数值仅取决于模式串本身而和相匹配的主串无关。我们可从分析其定义出发用递推的方法求得我们可从分析其定义出发用递推的方法求得next函数值。函数值。求next函数值的过程是一个递推过程，分析如下:已知已知:next1=0next1=0；（）；（）假设假设:nextj=k；有有 :P:P1 1P P2 2PPk-1k-1=PPj-k+1j-k+1P Pj-k+2j-k+2PPj-1j-1 （）（）其中其中k为满足为满足kk满足等式满足等式(4-7)。这时，。这时，nextj=?可能存在两种情况：情况一：情

10、况一：若若:P Pk k=P Pj j，则表明在模式串中存在，则表明在模式串中存在，P P1 1P P2 2PPk k=PPj-k+1j-k+1P Pj-k+2j-k+2PPj j（）（）且且不可能存在kk满足等式(4-8)，也就是说，也就是说nextj+1=k +1，即即nextj+1 =nextj +1=k+1情况二：情况二：Pk k Pj j,则表明在模式串中P1 1P2 2Pk k Pj-k+1j-k+1Pj-k+2j-k+2Pj j 这时，可将求这时，可将求next函数值问题看作是一个模式匹配问题，整个模式串既是主串又是函数值问题看作是一个模式匹配问题，整个模式串既是主串又是模式串。

11、而当前在匹配过程中，已经有：模式串。而当前在匹配过程中，已经有：求next函数值的过程是一个递推过程，分析如下:有有 :P:Pj-k-1j-k-1=PP1 1 ,P Pj-k-2j-k-2=P P2 2，PPj-1 j-1=PPk k则当则当 Pk k Pj j 时,应将模式向右滑动至模式中的第nextk个字符和主串中第个字符和主串中第j 个字符相比较。若个字符相比较。若nextk=k，且，且pj=pk,则说明在主串中第则说明在主串中第j+1个字符之前存在一个长度为个字符之前存在一个长度为k（即（即nextk最长子串，最长子串，和模式串中从首字符起长度为和模式串中从首字符起长度为k 的子串相等

12、，即（P83）有有 :P:P1 1P P2 2PPkk=PPj-kj-k，P Pj j （1kkj)1kkj)（10）就是说，nextj+1=k+1 （4-11）同理，若Pj Pk，则将模式继续向右滑动直至将模式nextk 个字符和pj对齐，以此类推，直至pj和模式中某个字符匹配成功或者不存在任何k(1kj)满足等式(4-10)，则 next j+1=1 （4-12）根据下边的图4.6 中的模式串，已经求出前 6个字符的next函数值，现求next7？,因为next6=3，又因p6p3,则需比较p6和p1（因为next=，这相当于将子串模式向右滑动，由于p6p1,而且next1=0，所以，ne

13、xt7=，而p7=p1,则next8=2。j=5 j+1=6 a a a b c a c a b a 0 1 1 2 2 3设 nextj=k j=5,k=2则 next5=2P P1 1 P Pk-1 k-1=P Pj-k+1 j-k+1 P Pj-1j-1P P1 1=P P4 4若若 (1)P(1)Pj j=P Pk k P P2 2=P P5 5 有有 P P1 1 P P2 2=P P4 4 P P5 5 (P (P1 1 P Pk-1 k-1=P Pj-k+1 j-k+1 P Pj-1j-1)j-1=5 j=6 j-1=5 j=6 k-1=2 k-1=2 next6=3 next6

14、=3 nextj+1=nextj+1nextj+1=nextj+1 =k+1 =k+1 J=5J+1=6下面再用图示法举例说明求next函数值的匹配过程：这实际上也是一个匹配的过程这实际上也是一个匹配的过程;不同在于：部分不同在于：部分主串和模式串是同一个串主串和模式串是同一个串求next函数值的过程是一个递推过程，分析如下:已知已知:next1=0next1=0；假设假设:nextj=k；有有 :P:P1 1P P2 2PPk-1k-1=PPj-k+1j-k+1P Pj-k+2j-k+2PPj-1j-1(2)若若:P Pj j P Pk k则则:需往前回朔，检查需往前回朔，检查 P Pj j

15、=P P?综上所述，根据分析结果式(4-6)、(4-9)、(4-11)和(4-12)，仿照KMP算法，可以求出next函数值的算法，如算法4.7（p83）所示：void get_next(SString&T,int&next)/求模式串T的next函数值并存入数组next i=1;next1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;/get_next算法4.7的时间复杂度为O（m），通常模式串的长度要比主串的长度n 要小得多，因此，对整个匹配算法来讲，所增加的这点时间是值得的。还有一种特殊情况需要考虑：例如：S=aaab

16、aaaab T=aaaabnextvalj=00004nextj=01234 void get_nextval(SString&T,int&nextval)i=1;nextval1=0;j=0;while(i b max=a;else max=b;main()float a,b,max；scanf(“%f,%f”,&a,&b);if ab max=a;else max=b;201 行号起始地址起始地址长度长度10020181012091710222624103250171042671510528224.4.2 具体步骤：（1）建立图书的书号及书名表的数据结构；（2）根据图书名中的关键词，建立书

17、号索引及对应的的数据结构；（3）从图书文件中读入一个书目串；（4）从目串中提取所有关键词插入词表；（5）对词表的每一个关键词，在索引表中进行查找，并作相应的插入操作。重复上述的（3）、（4）和（5）。具体算法见P87-89。1 1、熟悉串基本操作的定义，并能利用这些基本操作来实熟悉串基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。现串的其它各种操作的方法。2 2、熟练掌握在串的定长顺序存储结构上实现串的熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。各种操作的方法。3 3、了解串的堆存储结构以及在其上实现串操作的、了解串的堆存储结构以及在其上实现串操作的基本方法。基本方法。第四章学习要点第四章学习要点、理解串匹配的、理解串匹配的KMPKMP算法，熟悉算法，熟悉NEXTNEXT函函数的定义，学会手工计算给定模式串的数的定义，学会手工计算给定模式串的NEXTNEXT函数值和改进的函数值和改进的NEXTNEXT函数值。函数值。5 5、了解串操作的应用方法和特点。、了解串操作的应用方法和特点。第四章结束第四章结束