利用C++实现字符串KMP模式下的匹配 加入using namespace std;

在C++中，Knuth-Morris-Pratt (KMP) 算法是一种高效的字符串匹配算法，用于在一个文本串中查找指定模式串的所有出现位置。利用`std`命名空间可以简化代码。以下是使用KMP算法实现的简单示例：

#include <iostream>
#include <vector>
using namespace std;

// KMP表的构造函数
vector<int> getKMPTable(string pattern) {
    int n = pattern.length();
    vector<int> lps(n, 0);
    for (int i = 1, j = 0; i < n; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = lps[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        lps[i] = j;
    }
    return lps;
}

// 主函数中应用KMP算法进行匹配
void kmpMatch(string text, string pattern) {
    vector<int> lps = getKMPTable(pattern);
    int i = 0, j = 0;
    while (i < text.length()) {
        if (text[i] == pattern[j]) {
            i++, j++;
        } else if (j > 0) {
            j = lps[j - 1]; // 如果当前字符不匹配，回退到lps数组对应的索引
        } else {
            i++; // 对于文本的第一个字符，只能往前移动一位
        }
        if (j == pattern.length()) {
            cout << "Pattern found at index " << i - j << endl;
            j = lps[j - 1]; // 回退以便继续搜索
        }
    }
    if (j != pattern.length()) {
        cout << "Pattern not found in the text" << endl;
    }
}

int main() {
    string text = "ABABDABACDABABC";
    string pattern = "ABCD";
    kmpMatch(text, pattern);
    return 0;
}