设主串为S，模式为T，写出kmp算法的匹配过程 主串为’‘aababcaabaabccb’’ 模式为’'aabaabc 用c++写出

KMP (Knuth-Pratt) 算法是一种高效的字符串匹配算法，用于查找主串S中是否存在给定的模式串T。以下是KMP算法的基本匹配过程：

1. **构建失配表**: KMP算法的关键在于提前计算出模式串T的失配表，即当前字符与前缀不匹配时需要跳过的最大距离。对于模式'aabaabc'，失配表会是这样的：
- 查看'a': 0
- 查看'a': 1
- 查找'aa': 2 (因为前两个'a'匹配了)
- 查找'aab': 2 (由于前缀'aa'已经处理过，加上当前的'a'共3位，但还是不匹配，所以跳过3位)
- 查找'aaba': 2 (同理，从'aa'开始算，加上一个'a'共4位，还不匹配，跳过4位)
- 查找'aabaab': 2 (继续，加了一个'b'还是不匹配，跳过5位)
- 查找'aabaabc': 2 (最后的'c'与'aab'相比位置更远，跳过6位)

2. **实际匹配过程**: 遍历主串S，每次移动到下一个字符并检查是否与模式串T的当前字符匹配。如果不匹配，根据失配表决定主串应该跳过多远。

假设我们从S的起始位置开始，步骤如下：
- S: aababcaabaabccb
- T: aabaabc

- 第1轮：
- S(0): a != T(0), 跳过0位（失配表：0）
- S(1): a == T(1), 继续
- S(2): b != T(2), 跳过2位（失配表：2）
- S(4): a == T(3), 继续
- S(5): b != T(4), 跳过2位（失配表：2）
...

- 这样，算法会逐个比较，直到找到模式串的完整匹配或者遍历完主串。

**C++代码示例**:

#include <vector>
using namespace std;

int getPrefixFunction(string pattern) {
    int prefix[Pattern.size() + 1];
    for (int i = 1; i < pattern.length(); ++i) {
        int j = prefix[i - 1];
        while (j > 0 && pattern[i] != pattern[j])
            j = prefix[j - 1];
        if (pattern[i] == pattern[j]) 
            j++;
        prefix[i] = j;
    }
    return prefix;
}

void kmpMatch(string text, string pattern) {
    vector<int> prefix = getPrefixFunction(pattern);
    int j = 0;
    for (int i = 0; i < text.size(); ++i) {
        while (j > 0 && text[i] != pattern[j])
            j = prefix[j - 1];
        if (text[i] == pattern[j])
            j++;
        if (j == pattern.size()) {
            cout << "模式在主串中的位置: " << i - j + 1 << endl;
            j = prefix[j - 1]; // 如果有匹配，回到前一个公共部分进行重新匹配
        }
    }
}

int main() {
    string S = "aababcaabaabccb";
    string T = "aabaabc";
    kmpMatch(S, T);
    return 0;
}

运行这段代码，你会看到模式"aabaabc"在主串中的位置信息。如果找不到匹配，则不会有任何输出。