KMP算法next函数?这个 next函数具体指的是什么?它是怎么求的?原理是什么?请大家不要复制粘贴

KMP算法next函数?这个 next函数具体指的是什么?它是怎么求的?原理是什么?请大家不要复制粘贴
KMP算法next函数?
这个 next函数具体指的是什么?它是怎么求的?原理是什么?
请大家不要复制粘贴

KMP算法next函数?这个 next函数具体指的是什么?它是怎么求的?原理是什么?请大家不要复制粘贴
设主串为S = "s1s2 ... sn",模式为T = "t1t2 ... tm"
当“失配”(si tj)时,模式串T “向右滑动” 的可行距离有多远? 或者说,下一步si 应该与模式串中的哪个字符比较,这完全取决于模式串,与主串无关
因此,可以预先为模式串设定一个数组next[j],当“失配” (si tj)时,i 不变,j 改为next[j]
0 当j = 1时,不比较
next[j] = max{k, 1