假设p订失配后只需要和pk继续比较 匹配 k5k+1…P 失配S[i]!=Pi i-k Di-k+1 匹配 PkI=PK j-h k+1…Ij-1 i-ki-k+1…i-1 nextEl=k ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 11 中国科学技术大学 S P i j 失配S[i]!=P[j] 匹配 Pj-kPj-k+1…Pj-1 = Si-k Si-k+1… Si-1 k 匹配 P0P1…Pk-1 = Si-k Si-k+1… Si-1 P0P1…Pk-1=Pj-kPj-k+1…Pj-1 next[j]=k 假设p[j]失配后只需要和p[k]继续比较
⑧匹配模式的改进算法(KMP算法) nextlI=1max{k0<k且po…Pk1=p1kp1 nextlI表示当模式中第个字符与主串失配时,在模式 中需要重新和主串该字符进行比较的字符位置 0123456 模式串 abcabcd nextel 000123 ypb@ustc.edu.cn 12 中国科学技术大学
ypb@ustc.edu.cn 12 中国科学技术大学 -1 j=0 next[j]= max{k|0<=k<j 且 ‘p0…pk-1 ’=‘pj-k…pj-1 ’} next[j]表示当模式中第j个字符与主串失配时，在模式 中需要重新和主串该字符进行比较的字符位置 匹配模式的改进算法(KMP算法) j 0 1 2 3 4 5 6 模式串 a b c a b c d next[j] -1 0 0 0 1 2 3
(算法57 基于KMP的模式匹配算法 int find KMP(char * S, char* P, int start =start ;j=0 while(istrlen(s)&& j<(int)strlen(P)i if(j==-1S[一=P[j){++i+j} else ]-nextii2 if(j=strlen (P)) return(i-1; else return -1 ypb@ustc.edu.cn 13 中国科学技术大学
ypb@ustc.edu.cn 13 中国科学技术大学 算法5.7 基于KMP的模式匹配算法 int find_KMP(char *S,char *P,int start){ i=start; j=0; while(i<strlen(S) && j<(int)strlen(P)){ if(j==-1 || S[i]==P[j]){++i;++j} else j=next[j]; } if(j=strlen(P)) return (i-j); else return -1; }
③Nex数组如何获取 Next=k P j-krj-k+1…rj- PLE==Plk PLJ!=PLk Next[j+1]=k+ PLI==PIk]? k=next[k] P[j]==P[k] PLJ!=PIK] Nextj+1=k+ P[j]=P[k”]? k=next ypb@ustc.edu.cn 14 中国科学技术大学
ypb@ustc.edu.cn 14 中国科学技术大学 Next数组如何获取 P j P[j]==P[k] Next[j+1]=k+1 Next[j]=k P0P1…Pk-1 = Pj-k Pj-k+1… Pj-1 k P[j]!=P[k] P[j]==P[k’]? k’=next[k] k’ P[j]==P[k’] Next[j+1]=k’+1 P P P[j]!=P[k’] P[j]==P[k’’] ? k’’=next[k’] … …