《KMP算法中next算法执行过程》由会员分享,可在线阅读,更多相关《KMP算法中next算法执行过程(17页珍藏版)》请在金锄头文库上搜索。
1、 int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S)i = pos; j = 1;while (i T0) return i-T0; / 匹配成功else return 0; / Index_KMPKMP(D.E.Knuth, V.R.Pratt,J.H.Morris) 算法如匹配过程中,当 Si Tj不匹配时,i不移动的情况下,j移动到k的位置进行下一轮比较。也就是如果当前元素序号为j+1,则nextj+1值的得出 要查看它的前一个元素j的next值(为k), 并且根据Tj和Tk是否相等来界定。 这实际上也是一个匹配
2、的过程。 不同在于:主串和模式串是同一个串。next函数值的递推过程,分析如下:已知:next1 = 0; 假设:nextj = k;又 Tj = Tk 则: nextj+1 = k+1若: Tj Tk 则需按照前面方法往前回朔,检查 Tj = T ?原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第1轮循环,i=1,j=0: void get
3、_next(SString next1 = 0; j = 0;while (1 T0) if (j = 0 | T1 = T0) i=i+1=2; j=j+1=1; next2 = 1; / get_next位序123456789T串abaabcabcNext值01ji第1轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第2轮
4、循环,i=2,j=1: void get_next(SString / get_next位序123456789T串abaabcabcNext值01ji第2轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第3轮循环,i=2,j=0: void get_next(SString j=j+1=1; next3 = 1; / get_
5、next位序123456789T串abaabcabcNext值011ji第3轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第4轮循环,i=3,j=1: void get_next(SString j=j+1=2; next4 = 2; / get_next位序123456789T串abaabcabcNext值0112ji第4
6、轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第5轮循环,i=4,j=2: void get_next(SString / get_next位序123456789T串abaabcabcNext值0112ji第5轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while
7、 (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第6轮循环,i=4,j=1: void get_next(SString j=j+1=2; next5 = 2; / get_next位序123456789T串abaabcabcNext值01122ji第6轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; n
8、exti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第7轮循环,i=5,j=2: void get_next(SString j=j+1=3; next6 = 3; / get_next位序123456789T串abaabcabcNext值011223ji第7轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next
9、例题:求T串abaabcabcnext函数值的递推过程 :第8轮循环,i=6,j=3: void get_next(SString / get_next位序123456789T串abaabcabcNext值011223ji第8轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第9轮循环,i=6,j=1: void get_nex
10、t(SString / get_next位序123456789T串abaabcabcNext值011223ji第9轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第10轮循环,i=6,j=0: void get_next(SString j=j+1=1; next7 = 1; / get_next位序123456789T串ab
11、aabcabcNext值0112231ji第10轮执行 完毕结果:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第11轮循环,i=7,j=1: void get_next(SString j=j+1=2; next8 = 2; / get_next位序123456789T串abaabcabcNext值01122312ji第11轮执行 完毕结果
12、:原函数: void get_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next例题:求T串abaabcabcnext函数值的递推过程 :第12轮循环,i=8,j=2: void get_next(SString j=j+1=3; next9 = 3; /由于i=9=T0,循环结束 / get_next位序123456789T串abaabcabcNext值011223129ji第12轮执行 完毕结果:也就是如果当前元素序号为j+1,则nextj+1值的得出 要查看它的前一个元素j的next值(为k), 并且根据Tj和Tk是否相等来界定。 这实际上也是一个匹配的过程。 不同在于:主串和模式串是同一个串。通过前面例题,大家总结下next函数值 的递推过程,是否如下所示?已知:next1 = 0 假设:nextj = k;又 Tj = Tk 则: nextj+1 = k+1若: Tj Tk 则需按照前面方法往前回朔,检查 Tj = T ?