本文共 2893 字，大约阅读时间需要 9 分钟。

KMP���������������������������������

������������KMP������������������������������������������������������������������������������������������������������������������������������������������������������������

KMP������������������������������������������������next������������������������������������������������������������������������������������������������������������������������next���������������������������

void get_next(char* p) {
    int len = strlen(p);
    next[0] = -1;
    int k = -1, j = 0;
    while (j < len - 1) {
        if (k == -1 || p[k] == p[j]) {
            k++;
            j++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

������������������������������������������������������������������������������

������������������������������

int kmp(char* s, char* p) {
    int s_len = strlen(s);
    int p_len = strlen(p);
    int i = 0, j = 0;
    while (i < s_len && j < p_len) {
        if (j == -1 || s[i] == p[j]) {
            j++;
            i++;
        } else {
            j = next[j];
        }
    }
    return j >= p_len ? i - j : -1;
}

���������������������������������������������

• ���������������������������i - j������������������������������
• ���������������-1������������������

������������������������������������

���������������������abcabc���������abc���������������������next������������������������

next[0] = -1,
next[1] = 0,
next[2] = 0,
...

���������������������������������������������������������������������

������main���������������������

int main() {
    char str[] = "bbc abcdab abcdabd";
    char pat[] = "abcdabd";
    int len_pat = strlen(pat);
    get_next(pat);
    
    cout << "���������: ";
    int ret = kmp(str, pat);
    cout << ret << endl;
}

������������get_next(pat)���������pat���������next���������kmp(str, pat)���������������������������0������������������

���������������������������������������������������������KMP������������������������������������������������������������������������������

���������������vala������������������������������������������������������������