假设pli失配后只需要和p[k]继续比较S匹配Pj-kPji-k+1...Pji-I=P失配S[i]!=P[i]Si-k Si-k+1... Si-K匹配PoP....Pk-1=PoPi...Pk-1-Pi-kPi-k+1... Pij-1Si-k Si-k+1... Si-1next[i]=k11中国科学技术大学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算法）-1j-0nextli]=max{k/0<=k<j 且“Po... Pk-1'=pj-k..Pj-])nextli表示当模式中第i个字符与主串失配时，在模式中需要重新和主串该字符进行比较的字符位置2134560jbbd模式串caca012300-1next[i]12中国科学技术大学ypb@ustc.edu.cn
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-O;Owhile(i<strlen(S) && j<(int)strlen(P)if(j==-1 1l S[i]==P[i]){++i;++j)else j-next[i];if(j=strlen(P)) return (i-i); else return -1;13中国科学技术大学ypb@ustc.edu.cn
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数组如何获取jPNext[i]=kKPPoP...Pk-l=Pi.k Pi+.. j.11P[i]=-P[k]Next[j+1]=k+1P[i]!-P[k]P[i]--P[k']?Pk'=next[k]P[i]!-P[k']P[i]==P[k']P[i]=-P[k"] ?Next[i+1]=k'+1k"=next[k']14中国科学技术大学ypb@ustc.edu.cn
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’] .