求特征向量N(例2) 算法3-15】计算特征向量N ntm= P strlen(;//m为模板P的长度 P= ntm;∥/动态存储区开辟基数数组 前缀 ababa aaaa assert(NI=0);∥若开辟存储区域失败,返出 N[O]=0; for(inti=1;i<m;i++)//分析P的每个位量 N=回p2so2|3国 intk=N[-1]/第(-1)位置的最长前缀串长度 next 大卿血端_权,究 北京大单啦检写@有,赖职 【算法3-16】KMP模式匹配 //以下 while语句递推决定合适的前緞位量k while( k>0&& P[O]I= P[k]) tartine)t t(String S, String P, int*N, /假定事先已经计算出P的特征数组N,作为轴入参数 /根据P[]比较第k位量前缀字符,决定N[ if(P[]== Plk]) /s末尾再倒数一个模板长度位置 N[]=k+1; int LastIndex =Sstrlen()-Pstrlen N[]=0; eturn(-1);∥/ startindex过大,匹配无法成功 return N /i是指向s内部字符的游梅 】是指向P内部字符的游标,@e 大带_息 张写 积新有,神 张所有,赖 34.3KMP模式匹配算法效率 KMP模式匹配示例(一) ∥S游标循环加1 for(i startindex; i< Sstrlen (; i++)t /若当前位置的字符不同,则用N循环求当前的j, 用于将P的恰当位置与s的位置对准 =N[-1] /P[]与S[门]相同,继续下一步循环 6j=6,N1]=4 ==S[])j+ 匹配成功,返回该S子串的开始位置 labababs bi=B j=6, NU-1=4 if(j== Pstrlen) a|bab》l =10,j=6 9 return(-1);/P和整个匹配失败,函敷返回值为 b ab b 张储帖写 真大带健意张写c所有,邮必究7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 back next 求特征向量N(例2) N = 1 2 3 4 5 P = b a b a b a a 0 12 3 4 5 6 a c b 789 0 1 2 前缀→ a 0 0 a a a 3 1 1 b a b a a b 10 11 12 a a a 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 back next 【算法3-15 】计算特征向量N int *Next(String P) { int m = P.strlen(); //m为模板P的长度 assert( m > 0); //若m＝0，退出 int *N = new int[m]; // 动态存储区开辟整数数组 assert( N != 0); //若开辟存储区域失败，退出 N[0] = 0; for( int i =1 ; i < m ; i++ ) //分析P的每个位置i { int k = N[i-1]; //第(i-1)位置的最长前缀串长度 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 back next //以下while语句递推决定合适的前缀位置k while( k > 0 && P[i] != P[k] ) k = N[k-1]; //根据P[i]比较第k位置前缀字符，决定N[i] if(P[i] == P[k]) N[i] = k+1; else N[i] = 0 ; } return N; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 back next 【算法3-16】KMP模式匹配 int KMP_FindPat(String S, String P, int *N, int startindex) { //假定事先已经计算出P的特征数组N，作为输入参数 // S末尾再倒数一个模板长度位置 int LastIndex = S.strlen() - P.strlen(); if ((LastIndex - startindex) < 0) return (-1); //startindex过大，匹配无法成功 int i; // i 是指向S内部字符的游标， int j = 0; // j 是指向P内部字符的游标， 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 back next 3.4.3 KMP模式匹配算法效率 // S游标i循环加1 for (i = startindex; i < S.strlen(); i++) { //若当前位置的字符不同，则用N循环求当前的j， //用于将P的恰当位置与S的i位置对准 while (P[j] != S[i] && j > 0) j = N[j-1]; //P[j]与S[i]相同，继续下一步循环 if (P[j] == S[i]) j++; //匹配成功，返回该S子串的开始位置 if( j == P.strlen()) return (i - j +1); }; return (-1); //P和S整个匹配失败，函数返回值为负 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42 back next KMP模式匹配示例（一） S = a b a b a b a b a b a b b P = a b a b a b Xb √ a b a b a b Xb a b a b a b Xb a b a b a b b i=6,j=6, N[j-1]=4 i=8,j=6, N[j-1]=4 i=10, j=6, j’=4 P = a b a b a b b 0 12 3 4 5 6 N = 0 0 1 2 3 4 0 0 1 2 3 4 5 6 7 8 9 10 11 12