关于KMP算法中next和nextval的算法思路
一,关于next的求法
就是比较从0到当前值减一是否有相同值(即正着看和倒着看对比),最后结果加一。
直接上图:
求abaabc的next值和aabaabaabaac的next值
留一个小问题可以自己试着做一下,串“ababaaababaa”的next值为011234223456。
二,关于nextval的求法
nextval根据next值求,如果x位置和next[x]的字符相同,则nextval[x]=nextval[next[x]],否则nextval[x]=next[x]
(或者可以理解为相同则变,不同不变)
直接上图:
求ababaabab的nextval值
可能这篇文章文字描述较少,只要把两幅图看懂,就可以做题了。
如果还没看懂,可以私聊我,再亲自教你