[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[i]，就是 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} 计算完毕。

对应代码如下：

#define MAX_SIZE 10

typedef struct {
    char str[MAX_SIZE];
    int len;
} SString;

void get_next(SString t, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < t.len) {
        if (j == 0 || t.str[i] == t.str[j]) {
            ++i;
            ++j;
            next[i] = j; // 若 pi=pj，则 next[j+1]=next[j]+1
        } else {
            j = next[j]; // 否则 j=next[j]
        }
    }
}

这是为数不多的让我感觉困惑的算法了，确实很有难度，逻辑很绕，多品味几次还是能搞懂的。