[C算法]006-KMP算法

求 next 数组

按照 next 数组访问字符串下标的做法求 next 数组

以 a b a a b c 为例，next[] 数组下标从 1 开始
首先，next 数组以 0 1 开头，i 是当前求的下标，j 是寻找要匹配下标。

1. next={0,1}，求 next[3]，i=2，j=next[i]，就是 j=1
   • i=2，j=1，对比 $p_2(b)!=p_1(a)$，匹配失败 ❌
   • 然后 j=next[j]，就是 j=0
   • 触发 j=0，直接 next[3]=1。
2. next={0,1,1}，求 next[4]，i=3，j=next[i]，就是 j=1
   • i=3，j=1，对比 $p_3(a)==p_1(a)$，匹配成功 ✅，所以 next[4]=j+1，就是 2。
3. next={0,1,1,2}，求 next[5]，i=4，j=next[i]，就是 j=2
   • i=4，j=2，对比 $p_4(a)!=p_2(b)$ 匹配失败 ❌
   • 然后 j=next[j]，就是 j=1。
   • 然后再对比 p_4(a)==p_1(a) 匹配成功 ✅，所以 next[5]=j+1，就是 2。
4. next={0,1,1,2,2}，求 next[6]，i=5，j=next[5]，就是 j=2
   • i=5，j=2，对比 $p_5(b)==p_2(b)$，匹配成功 ✅，所以 next[6]=j+1 就是 3。
5. next={0,1,1,2,2,3} 计算完毕。