假设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]继续比较