C++算法庫中的KMP字符串匹配

KMP算法（Knuth-Morris-Pratt算法）是一種用于字符串匹配的算法，用于在一個文本串中查找一個模式串的出現(xiàn)位置。KMP算法的主要思想是利用已經匹配過的信息來盡量減少比較的次數(shù)。

以下是一個簡單的C++實現(xiàn)KMP字符串匹配的示例代碼：

#include <iostream>
#include <vector>

void computeLPSArray(std::string pattern, std::vector<int>& lps) {
    int M = pattern.length();
    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(std::string text, std::string pattern) {
    int N = text.length();
    int M = pattern.length();
    
    std::vector<int> lps(M, 0);
    computeLPSArray(pattern, lps);
    
    int i = 0, j = 0;
    while (i < N) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == M) {
            std::cout << "Pattern found at index " << i - j << std::endl;
            j = lps[j - 1];
        } else if (i < N && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    
    KMP(text, pattern);
    
    return 0;
}

在上面的代碼中，computeLPSArray函數(shù)用于計算模式串的最長前綴后綴數(shù)組（LPS），KMP函數(shù)用于在文本串中查找模式串的出現(xiàn)位置。通過以上代碼，您可以在C++中實現(xiàn)KMP算法來進行字符串匹配。