Question

KMP算法next函数?

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

Answer 1

设主串为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 <= k < j 且"t1 … tk-1" = "tj-(k-1) … tj-1"}
1 其他情况

next[j] 函数表征着模式T 中最大相同首子串和尾子串(真子串)的长度
相似部分越多，则next[j] 函数越大
既表示模式T 字符间的相关度越高，也表示j 位置以前与主串部分匹配的字符数越多
next[j] 越大，模式串向右滑动得越远

Answer 2

next函数是0123。
那个滑动不是那么滑的吧。
因为next[4]=3,所以
主串的第四个值和子串的第三个值对应。也就是向右滑动1个字