《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 ？
