②KMP算法的推导过程：（见教材P81）抓住部分匹配结果的两个特征：
i
S=?a b a b cabc a c b a b?
T=?abc a c?
ki设目前应与T的第k字符开始比较则T的k-1～1位＝S前i-1～i-(k-1)位
即(4-2）式含义
S=?a b a b c abc a c b a b?刚才肯定是在S的i处和T的第j字符处失配
T=?a b c ac?则S前i-1～i-(k-1)位＝T的j-1～j-(k-1)位
k
j
即(4-3）式含义
两式联立可得：‘T1…Tk-1?=?Tj-(k-1)…Tj-1?
注意：j 为当前已知的失配位置，我们的目标是计算新起点k，仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！
②KMP算法的推导过程(续）：
根据模式串T的规律：‘T1…Tk-1?=?Tj-(k-1)…Tj-1?
和已知的当前失配位置j ，可以归纳出计算新起点k的表达式。令k = next[ j ]，则
0 当j＝1时
next[ j ]＝max { k |1 1 其他情况讨论： ①next[ j ]有何意义？ 一旦失配，应从模式串T中第next[ j ]个字符开始与S的失配点i 重新匹配! ②next[ j ]怎么求？ 后面会举例（参见教材P81） ③KMP算法的实现—即Index( )操作的实现（见教材P82） 第一步，先把模式T所有可能的失配点j所对应的next[j]计算出来；第二步：执行定位函数index_kmp （与BF算法模块非常相似） Int Index_KMP(SString S, SString T, int pos) {i=pos; j=1; while ( i<=S[0] && j<=T[0] ) { if (j==0|| S[i] = = T[j] ) {++i, ++j} //不失配则继续比较后续字 符 else {j=next[j];} //S的i指针不回溯，从T的k位置开始匹配 } if(j>T[0]) return i-T[0]; //子串结束，说明匹配成功else return0;}//Index_KMP 怎样计算模式T所有可能的失配点j 所对应的next[j]？ 例：模式串T：a b a a b c a c可能失配位j：1 2 3 4 5 6 7 8新匹配位next[j]:01122312刚才已归纳：讨论： 0 当j＝1时 next[ j ]＝max { k |1 1 其他情况 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 j=5T3? 时, k={2，3，4}，要查看‘T1?=?T4? 、‘T1T2?=?T3T4? 和 ‘T1T2T3?=?T2T3T4? 以此类推，可得后续next[j]值。 讨论两个有关next [ j ]的问题： ①怎样简捷计算next[j]？可用递推法编程实现！（参见P83简捷算法）计算next[j]的时间为O(m) void get_next(SString T, int &next[ ] ){ //next函数值存入数组nexti=1; next[1]=0; j=0;while(i if(j= = 0||T[i]= = T[j]){++i;++j;next[i]=j;}else j=next[j];} }// get_next ②next [ j ]是否完美无缺？void get_nextval(SString T, int &nextval[ ] ){ //next函数修正值存入数组nextval答：未必，例如当 i=1; nextval[1]=0; j=0; S=?a b a a a a b?,while(i else nextval[i]=nextval[j]; }（参见P84改进算法, else j=nextval[j]; }称为nextval [ j ] ） }// get_nextval 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构课件- 河南大学精品课程网 - 图文 -(5)在线全文阅读。
相关推荐：