KMP字串比對演算法

• (假設在S中找T，因為T[0] != T[...], 若T[0] == S[0], T[1] == S[1]..., 就可以跳過)

j = 字串長度
0, j = 1
next[j] = Max{k| 1 < k < j, 且P(1)...P(k-1) == P(j-k+1)...P(j-1)}
1, others

// Get next array
void get_next(String T, int *next) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T[0]) { // T[0]為字串長度
        if (j == 0 || T[i] == T[j]) {
            i++;
            j++;
#if !defined(改良版)
            next[i] = j;
#else
            // 如果a位元字元與其next值指向的b位元字元相等，next[a]指向next[b]
            // 如果不相等，next[a]指向next[a]
            if (T[i] != T[j])
                next[i] = j;
            else
                next[i] = next[j];
#endif
        } else {
            j = next[j];
        }
    }
}

int Index_KMP(String S, String T, int pos) {
    int i = pos;
    int j = 1;
    int next[255];
    get_next(T, next);

    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j > T[0])
        return i - T[0];
    else
        return 0;
}

Example：

• 字串：ababaaaba
• 未改良next[]：011234223
• 經改良next[]：010104210