第4章 数据结构——串.pptVIP

* 怎样计算模式T所有可能的失配点 j 所对应的 next[j]？ 例： 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 next[j] : next[ j ]＝ 0 当j＝1时 max { k |1kj 且‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’ } 1 其他情况 0 1 1 2 2 3 1 2 讨论： j=1时, next[ j ]≡ 0；因为属于“j=1”; j=2时, next[ j ]≡ 1；因为属于“其他情况”； 刚才已归纳： j=3时, k={2}，只需查看‘T1’=‘T2’； j=4时, k={2，3}，要查看‘T1’=‘T3’ 和‘T1T2’=‘T2 T3’ j=5时, k={2，3，4}，要查看‘T1’=‘T4’ 、‘T1T2’=‘T3T4’ 和 ‘T1T2T3’=‘T2T3T4’ 以此类推，可得后续next[j]值。 * 怎样简捷计算next[j]？ 可用递推法编程实现！ （参见P83简捷算法） 计算next[j]的时间为O(m) 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]; } }// get_next * 讨论： next[ j ]有何物理意义？ next[j]函数表征着模式中两段字符之间相匹配的最大子串的长度（除串本身外）。 可见，模式中相似部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。 next[ j ]＝max { k |1kj 且‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’ } 模式串从首位往右直到K-1位 模式串从j的前一位往左直到K-1位 想一想：如果主串和模式均为二进制码流，用KMP算法效果如何？ * next函数的改进算法 前面定义的next函数在某些情况下还是有缺陷 例如：模式aaaab与主串aaabaaaab匹配情况： 模式： a a a a b j：1 2 3 4 5 next[j]： 0 1 2 3 4 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 * 当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]] 修改算法见教材P84 算法4.8 此时效率不高的原因为： * Nextval函数 j=1时，nextval[j]=0; j1时， 若pj= pnext[j]，则nextval[j]=nextval[next[j]]; 若pj!= pnext[j]，则nextval[j]=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]; } }// get_next void get_nextval(SString T, int nextval[ ] ){ //next函数修正值存入数组nextval i=1; nextval[1]=0; j=0; while(iT[0] ){ if(j= = 0||T[i]= =T[j] ){ ++i;++j; if(T[i]!=T[j] ) nextval[i]=j; else nextval[i]=nextval[j]; } els