数据结构与算法串

1、华中农业大学理学院 章 英 数据结构与算法 2/44第十讲 模式匹配本讲知识点：本讲知识点： (1)熟悉串的模式匹配的简单算法熟悉串的模式匹配的简单算法 (2)掌握改进的模式匹配算法的具体实现掌握改进的模式匹配算法的具体实现 (3)掌握串的应用问题掌握串的应用问题重点：重点：串的应用串的应用难点：难点：改进的模式匹配算法改进的模式匹配算法3/44在最坏情况下，第在最坏情况下，第i 趟匹配成功，前面趟匹配成功，前面i-1趟的不成功的趟的不成功的匹配中，每趟比较了匹配中，每趟比较了m次，第次，第i 趟成功时也比较了趟成功时也比较了m次次，所以共比较了，所以共比较了i m次。因此在最坏情况下，平均比

2、次。因此在最坏情况下，平均比较次数是：较次数是：由于由于nm，故上述的时间复杂度为故上述的时间复杂度为O(mn)2/ )2()1/()(1111mnmimnmmiPmnimnii匹配算法分析4/44简单匹配算法缺点在于每次不能匹配以后主串（目标串简单匹配算法缺点在于每次不能匹配以后主串（目标串）指针和子串（模式串）指针都必须回溯，造成了这种）指针和子串（模式串）指针都必须回溯，造成了这种算法的时间复杂度为算法的时间复杂度为O(m*n)。而而KMP算法使得主串指针不必回溯而只需回溯模式串算法使得主串指针不必回溯而只需回溯模式串指针，并且模式串指针也不一定需要回溯到模式串的第指针，并且模式串指针也

3、不一定需要回溯到模式串的第一个字符，一个字符，KMP算法的时间复杂度为算法的时间复杂度为O(m+n)。 例如，当例如，当 T=“0000000000000000000000000000001” P=“000001” 时，时，KMP算法比简单算法效率要高的多。算法比简单算法效率要高的多。模式匹配的改进模式匹配的改进5/44一、一、KMP算法算法 T a b a a b a b P a b a b | | |第第1趟趟 P a b a b |第第3趟趟 T a b a a b a b| P a b a b 第第2趟趟 T a b a a b a b省略第省略第2趟趟直接进行直接进行t3和和p2的比

4、较的比较6/44一、一、KMP算法算法 P a b a b T a b a a b a b|已知已知p1=t1，而，而p0p1，那么，那么p0t1由于由于p0=p2，所以，所以t2=p07/44abadabd?0taba0pdabcacbabapdabij匹配失败匹配失败! !基本思想基本思想8/44比较到第比较到第i+1趟匹配时，如果比较到趟匹配时，如果比较到P中第中第j个字个字符时不匹配。即：符时不匹配。即：tpi+jtiti+1 . ti+j-1jp0p1 . pj-1第第i+1趟趟ti+jpj接下来用接下来用p0和和ti+1开始比较，若匹配成功则如下开始比较，若匹配成功则如下tpti+

5、1ti+2 . ti+j ti+mp0p1 . pj-1 pm-1第第i+2趟趟9/44tpi+jtiti+1 . ti+j-1jp0p1 . pj-1第第i+1趟趟ti+jpjpp0p1 .pj-2p1p2 . pj-1p假设假设ti+1ti+2 .ti+j-1由此，第由此，第i+2趟匹配可以跳过不做。趟匹配可以跳过不做。仅考察仅考察模式串模式串分析分析10/44第第i+3趟匹配是否需要进行呢？趟匹配是否需要进行呢？tpi+jtiti+1 . ti+j-1jp0p1 . pj-1第第i+1趟趟ti+jpj假设假设模式串模式串pp0p1 .pj-3p2p3.pj-1p假设假设ti+2ti+3

6、.ti+j-1由此，第由此，第i+3趟匹配可以跳过不做。趟匹配可以跳过不做。11/44依此类推，直到对于某值依此类推，直到对于某值k，使得，使得p0p1.pk pj-k-1pj-kpj-1 而而p0p1.pk-1 = pj-kpj-k+1pj-1ti+jtiti+1.ti+j-1pp0p1.pkk+1jpj-k-1pj-k.pj-1p0p1.pk-1pj-kpj-k+1.pj-1=pki+j12/44假设主串为：假设主串为： t1t2.tn模式串为：模式串为： p1p2.pm我们要解决的问题是：当我们要解决的问题是：当“失配失配”(ti pj)时，模式时，模式串串“向右滑动向右滑动”的可行距离

7、有多远；或者说，下一的可行距离有多远；或者说，下一步步ti应该与模式串中的哪个字符比较应该与模式串中的哪个字符比较?可知：可知：答案将完全取决于模式串，而与主串无关答案将完全取决于模式串，而与主串无关因此：可以预先为模式串设定一个数组因此：可以预先为模式串设定一个数组nextj，当，当“失配失配”(ti pj)时，时，i不变，不变，j改为改为nextj。分析分析13/44j 0 1 2 3 4 5 6 7 模式串nextj a b a a b c a c -1 0 0 1 1 2 0 1nextj=Maxk|0kj且且P0Pk-1=Pj-kPj-k+1Pj-1 当此集合不空时当此集合不空时0

8、其他情况其他情况-1 当当j=0时时定义定义nextj例如：例如：14/44第第1趟匹配趟匹配 T a c a b a a b a a b c a c x P a b a a b c a c |i=1j=1 next1=0第第2趟匹配趟匹配 T a c a b a a b a a b c a c x P a b a a b c a c |i=1j=0 next0=-1第第3趟匹配趟匹配 T a c a b a a b a a b c a c x P a b a a b c a c |i=2j=0| | | | | i=7j=5 next5=2第第4趟匹配趟匹配 T a c a b a a b

9、a a b c a c x P a b a a b c a c i=13j=8| | | | | |i=7j=2 15/44int KMPIndexHelp(const String &T, const String &P, int pos, int next ) int i=pos, j=0; while( i T.Length() & j P.Length() if ( j = -1 ) i+; j=0; else if( Pj = Ti ) i+; j+; else j = nextj; if ( j P.Length() ) return -1; else return i-j;ijn

10、extjireturn算法实现算法实现16/44可以用递推的方法推出可以用递推的方法推出next的值。当的值。当j0时，时，next0=-1；设设nextj=k，即，即模式串模式串P中存在：中存在： p0p1.pk-1 = pj-kpj-k+1.pj-1其中其中k为满足为满足0k k满足上式，满足上式，因此因此nextj+1 = nextj+1 = k+1;pkjj+1计算计算next17/44abcdabcd如如next6=201234567P2P6则则next7=3举例举例18/44pkj2、若、若PkPj，此时可把求此时可把求nextj+1值的问题看作是一值的问题看作是一个模式匹配问题。

11、目标串和模式串都是个模式匹配问题。目标串和模式串都是P。由由nextj=k，可知：，可知： p0p1.pk-1 = pj-kpj-k+1.pj-1必须在必须在“P0P1Pk-1”中寻找使得：中寻找使得： p0p1.ph-1 = pk-hpk-h+1.pk-1 成立的最大的成立的最大的h。分两种情况：分两种情况：（1）找到）找到h（2）找不到）找不到h，则，则nextj+1=0h计算计算next19/44(1)若若Ph=Pj，则表明模式串，则表明模式串P中有：中有： p0p1.ph-1ph = pj-hpj-h+1.pj-1pj因此因此nextj+1 = h+1 = nextk+1=nextne

12、xtj+1;(2)若若PhPj，则再在，则再在“P0P1Ph-1”中寻找更小的中寻找更小的nexth=y。如此递推。直到如此递推。直到nextj+1=0，结束。，结束。pkjh计算计算next20/44j 0 1 2 3 4 5 6 7 模式串nextj a b a a b c a c-1 0 0 1 1 2 0 1已求得前已求得前6个字符的个字符的next函数值，现求函数值，现求next6。因为因为next5=2，又，又P5!=P2，则需比较，则需比较P5和和P0（因为（因为next2=0），这相当于将子串向右滑动。），这相当于将子串向右滑动。由于由于P5!=P0，而且，而且next0=-1

13、，所以，所以next6=0。而因为而因为P6=P0，则，则next7=next6+1=0+1=1。分析讨论分析讨论21/44void getNext(const String &P, int next ) next0 = -1; int j = 0, k = -1; while( j =0) sj+=stk-k ; sj=0; return s;算法实现算法实现40/44实战练习 POJ 2503 Description You have just moved from Waterloo to a big city. The people here speak an incomprehensi

14、ble dialect of a foreign language. Fortunately, you have a dictionary to help you understand them. words 10000041/44实战练习 Sample Input dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay Sample Output Cat eh loops 找不到的单词，输出找不到的单词，输出eh42/44#include#include /关联容器 推荐看书:C+ primerusing namespace std;maptk;int main() string a,b,c; unsigned i,k,t=0; while(getline(cin,c),c.find( )!=-1) /find返回字符在串里的下标位置 k=c.fi