模式匹配子串在主串中的定位操作PPT学习教案

1、会计学1 模式匹配子串在主串中的定位操作模式匹配子串在主串中的定位操作 2 t a b b b a a p 图3.3 朴素的模式匹配过程 a b a a b a a b a a b a 3.3.1 朴素的模式匹配朴素的模式匹配 模式匹配的最简单的做法是：用p中的字符依次与t中的字符比较：如果t0 = p0，t1 = p1，tm-1 = pm-1，则匹配成功，调用求子串的操作subStr(t,1,m)即是找到的子串。否则必有某个i（0im-1），使得ti pi，这时可将p右移一个字符，用p中字符从头开始与t中字符依次比较；如此反复执行，直到下面两种情况之一：或者到达某步时，ti = p0，ti+

2、1 = p1，ti+m-1 = pm-1，匹配成功，subStr(t,i+1,m)即是找到的（第一个）与模式p相同的子串；或者一直将p移到无法与t继续比较为止，则匹配失败。 第1页/共16页 3 主串： “000000000000000000000000000000000000000000001” 模式串： “00000001” 朴素匹配算法简单，易于理解，但效率不高，主 要原因是执行中有回溯，一旦比较不等，就将p所指的 串右移一个字符，并从p0（算法中用p-c0表示）开 始比较。在最坏的情况下，每趟比较都在最后出现不 等，最多比较nm1趟，总比较次数为m*(nm1)， 由于在一般情况下mn，

3、所以算法运行时间为 O(m*n)。 第2页/共16页 4 3.3.2 无回溯的模式匹配无回溯的模式匹配 由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的。简称KMP算法。 设主串S=“ababcabcacbab”, 模式串 T=“abcac”。 则普通算法的匹配过程如下： 第3页/共16页 5 第一趟匹配 第二趟匹配 第三趟匹配 第四趟匹配 第五趟匹配 第六趟匹配 a b a b c a b c a c b a b a b a b c a b c a c b a b a b a b c a b c a c b a b a b a b c a b c a c b a b

4、 a b a b c a b c a c b a b a b a b c a b c a c b a b a b c a c a b c a c a b c a c a b c a c a b c a c a b c a c 第4页/共16页 6 第一趟匹配 第二趟匹配 第三趟匹配 a b a b c a b c a c b a b a b a b c a b c a c b a b a b a b c a b c a c b a b a b c a c a b c a c (a)b c a c pitj 下一步p中哪个字符和tj比较？ Pk 0ki 第5页/共16页 7 1. k值仅依赖于p

5、本身的前个i字符，于目标t 无关； 2. 用nexti 表示与i对应的k值，其含义如下： nexti 0，pitj, pk(p nexti )与 tj比较。 nexti=-1，p0与 tj+1比较。 对任何模式p，只要确定nexti (i=0,1,m-1) 的值,当pitj时，直接右移i- nexti个字符， 使 pk(p nexti )与 tj比较 或使p0与 tj+1比较。 第6页/共16页 8 int index(PSeqString t,PSeqString p, int *next) int i,j; i=0; j=0;/*初始化*/ while (in j+; else i=nex

6、ti ;/* j = j - i + 1; i = 0; */ if (i=p-n) return( j - p-n + 1);/*匹配成功*/ else return( -1 );/*匹配失败*/ 第7页/共16页 9 k值仅依赖于值仅依赖于p本身前本身前i个字符个字符 t0tj-i-1tj-itj-1 tj p0pi-1pi t0tj-i-1 p0pi-1tj p0pi-1pi 图 3.54 发现pitj的状态 第8页/共16页 10 后缀 t0tj-i-1 p0 pi-kpi-1 tj p0 pk-1 pk 前缀 图 3.5 p0pi-1的前缀与其后缀比较 设p0pi-1中最大相同的前缀

7、与其后缀（不包括 p0pi-1本身，但允许空串）的长度为k(0ki-1)。 当pitj时，右移i-k位，使pk与 tj比较。 第9页/共16页 11 t0tj-i-1p0pj-1 tj p0pi-1pi t0tj-i-1 p0pi-k+1 pi-1 tj p0 pk-1pk pi tj , pi=pk , pk tj 。应再右移nextk 位。使p nextk与tj比较。 第10页/共16页 12 Nexti的求法：的求法： (1) 求p0, p1,pi-1 中最大相同的前缀与后缀的长 度k； (2) nexti=k. 当i=0时, 令nexti=-1. 若pk=pi,则pktj. 应再右移，

8、使pnextk与tj比较， 第2步改为： (2) if (pk= =pi) nexti=nextk; else nexti=k; 第11页/共16页 13 p0 pi-kpi-1 pi p0 pk-1 pk 图 3.6 检查长度为k的前后缀是否相等 令next0=-1,设p0 pi-kpi-1 中最大相同前后 缀 的长度是k。若pk = pi ，则p0 pi-kpi-1 pi中最 大相同前后缀的长度为k=k+1;否则，k=nextk.在计 算nexti时，利用了next0，, nexti-1. ？ 第12页/共16页 14 算法3.7 计算next数组 makeNext(PSeqString

9、p, int *next) /* 变量next是数组next的第一个元素next0的地址 */ int i, k; k= -1; i=0; next0= -1; /* 初始化 */ while (in-1)/* 计算 nexti+1 */ while (k=0 i+;k+; if(p-ci= =p-ck) nexti= nextk; else nexti = k; 第13页/共16页 15 KMP算法的优点：不需回溯。这对于从外设读 入的庞大文件很有效，可以边读入边匹配，无须回头 重读。无回溯匹配时间复杂性：O(n). 下标 i 0 1 2 3 4 5 6 7 8 p i a b c a a b a b c k 0 0 0 1 1 2 1 2 Pk与 pi比较 = = = = Nexti -1 0 0 -1 1 0 2 0 0 表3.1 计算next数组 p=“abcaababc” 第14页/共16页 16 小 结 串是特殊的线性表，是由字符作元素组成的。它和 线性表一样有顺序存储和链式存储两种方式。串作为 一种抽象数据类