C語言字符串查找中的KMP算法介紹

Knuth-Morris-Pratt（KMP）算法是一種高效的字符串匹配算法，由Donald Knuth、Vaughan Pratt和James H. Morris于1977年提出。KMP算法的核心思想是利用已經匹配的部分信息，避免在文本串中的回溯，從而提高字符串匹配的效率。

KMP算法的主要步驟如下：

1. 構建最長公共前后綴數組（也稱為部分匹配表）：這個數組用于存儲模式串（pattern）中每個位置的最長公共前后綴長度。例如，對于模式串"ABABAC"，最長公共前后綴數組為{0, 0, 1, 2, 0, 1}。

2. 在文本串（text）中進行匹配：從文本串的第一個字符開始，與模式串的第一個字符進行比較。如果相等，則繼續比較下一個字符；如果不相等，則根據當前模式串中已匹配的部分，查找最長公共前后綴數組，確定下一個需要比較的模式串字符的位置。重復這個過程，直到找到匹配的子串或者比較完整個文本串。

KMP算法的時間復雜度為O(n+m)，其中n為文本串的長度，m為模式串的長度。這使得KMP算法在處理大量數據時具有較高的效率。

以下是一個簡單的KMP算法實現（C語言）：

#include<stdio.h>
#include<string.h>

void compute_lps(char* pattern, int M, int* lps) {
    int len = 0;
    lps[0] = 0;

    int i = 1;
    while (i < M) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void kmp_search(char* text, char* pattern) {
    int N = strlen(text);
    int M = strlen(pattern);
    int lps[M];

    compute_lps(pattern, M, lps);

    int i = 0; // Index for text
    int j = 0; // Index for pattern
    while (i < N) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == M) {
            printf("Pattern found at index %d\n", i - j);
            j = lps[j - 1];
        } else if (i < N && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

int main() {
    char text[] = "ABABABCABABABC";
    char pattern[] = "ABABAC";
    kmp_search(text, pattern);
    return 0;
}

這段代碼首先計算了模式串"ABABAC"的最長公共前后綴數組，然后在文本串"ABABABCABABABC"中查找該模式串。運行結果將輸出"Pattern found at index 6"，表示在文本串中找到了模式串的匹配。