S 假设p[]失配后只需要和p[k继续比较 S 匹配 Pi-kPi-k+l..P-= 失配S[的]=P] Si-kSik1. Si-I 匹配 PoP1...Pk-I= Si-k Si-k+1Si- PoP1...Pk-I-Pi-kPj-k+1Pj-I next[j]=k ypb@ustc.edu.cn 11 中国科学技术大学
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算法 -1 j=0 next[j]= max{k0<=k≤j且‘po…pk-1’=p-k…p-'} next[]表示当模式中第j个字符与主串失配时，在模式 中需要重新和主串该字符进行比较的字符位置 j 0 2 3 6 模式串 a b a b d next[j] -1 0 0 0 2 3 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
算法4.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 ll S[i]==P[jl){++i;++j) else j=next[j]; if(j=strlen(P))return (i-j);else return-1; ypb@ustc.edu.cn 13 中国科学技术大学
ypb@ustc.edu.cn 13 中国科学技术大学 算法4.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; } 为何需要 强制转换
Next数组如何获取 P Next[j]=k PoP1...Pk-1= Pi-k PklP- P[]=P[k] P[il!=P[k] Next[j+1]=k+1 P[]=Pk]? k'=next[k] P[i]==P[k'] P[il!=P[k'] Next[j+1]=k'+1 P]=P[k"]? k”=next[k] 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’] … …