数据结构chap4.pptVIP

讨论两个有关next [j]的问题： 怎样简捷计算next[j]？ 答：可用递推法编程实现！（参见P83简捷算法） 计算next[j]的时间复杂度为O(m) 分析过程： （1）next[1]= 0 （2）假设 next[j]=k, 则说明模式串中存在下列关系： ‘p1……p k-1’ = ‘pj-k+1……p j-1’ 其中1kj, 且不可能存在k’k满足上式， 从而 next[j+1]=? 有两种情况： pk=pj , 即：‘p1……pk’ = ‘pj-k+1……pj’ 并且不可能存在k’k 满足上式，则 next[j+1] = k+1 即：next[j+1] = next[j]+1 pk≠pj ，即：‘p1……pk’ ≠ ‘pj-k+1……pj’ 此时可把求next[j+1]的问题也看成是一个模式匹配的问题，整个模式串既是主串又是模式串，而当前在匹配过程中，已有pj-k+1 = p1 ，pj-k+2 = p2 , ……. , pj-1= pk-1。 则当pk≠pj 时，应将模式向右滑动至模式中的第next[k] 个字符和主串中的第j个字符进行比较。 ? 若next[k] = k’, 且pk’ = pj ， 有 ‘p1……pk’’ = ‘pj-k+1……pj’ (1k’kj) 则 next[j+1] = k’+1, 即：next[j+1]= next[k]+1 ? 若next[k] = k’, 且pk’≠pj ，将模式串继续向右滑动直至将 模式中第next[k’]个字符和pj 对齐； …… 依次类推， 直至pj 和模式中某个字符匹配成功，或不存在任何k’（1k’j）满足等式 ‘p1……pk’’ = ‘pj-k+1……pj’ ， 则next[j+1] = 1。 i=1; j=0 next[1]=0 iT[0] j==0 || T[i]==T[j] ++i; ++j; next[i]=j; j=next[j]; 结束 Y Y N N 求解next[j] 算法流程图: void get_next (SString T, int next[ ] ) { //next函数值存入数组next[] i=1; next[1]=0; j=0; while(iT[0] ) { if ( j==0||T[i]==T[j] ) { ++i; ++j; next[i]=j; } else j=next[j]; } // while }//get_next j 1 2 3 4 5 6 7 8 模式 a b a a b c a c next[j] 0 1 1 2 2 3 1 2 S: a a a b a a a a b T: a a a a b i: 1 2 3 4 5 6 7 8 9 a a a a b a a a a b a a a a b a a a a b next [ j ]是否完美无缺？ 答：未必，例如当S=‘a b a a a a b’,T=‘a a a a b’时 ,仍有 多余的比较（参见P84改进算法,称为nextval[j]）。 j： 1 2 3 4 5 模式： a a a a b Next[j]： 0 1 2 3 4 当Pj==Pnext[j]时， 如果Si!=Pj，? Si!=Pnext[j] 因此，Si 没有必要继续与Pnext[j]进行比较， 而应该直接和Pnext[j]的下一个字符Pnext[next[j]] 进行比较。 所以，在计算next函数时，如果出现Pj=Pnext[j] = Pk 则next[j]=next[k]=next[next[j]]。 此时效率不高的原因为： void get_nextval(SString T, int nextval[ ] ) { //next函数修正值存入数组nextval[]