用C++ string类遍写KMP模式匹配算法

好的，可以的。KMP模式匹配算法是一种字符串匹配算法，可以在一个长文本串S内查找一个模式串P的出现位置，算法时间复杂度为O(n+m)，其中n为文本串S的长度，m为模式串P的长度。下面是用C++ string类实现的KMP模式匹配算法代码：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void build_next(string &P, vector<int> &next) {
    int m = P.length();
    next[0] = -1;
    int j = -1;
    for (int i = 1; i < m; i++) {
        while (j >= 0 && P[i] != P[j + 1]) {
            j = next[j];
        }
        if (P[i] == P[j + 1]) {
            j++;
        }
        next[i] = j;
    }
}

void KMP(string &T, string &P) {
    int n = T.length(), m = P.length();
    vector<int> next(m);
    build_next(P, next);
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && T[i] != P[j + 1]) {
            j = next[j];
        }
        if (T[i] == P[j + 1]) {
            j++;
        }
        if (j == m - 1) {
            cout << "Pattern occurs with shift " << i - m + 1 << endl;
            j = next[j];
        }
    }
}

int main() {
    string T = "AABAACAADAABAAABAA";
    string P = "AABA";
    KMP(T, P);
    return 0;
}

这段代码首先实现了KMP模式匹配算法的主体部分。build_next函数用于构建模式字符串P的next数组，next[i]表示P[0]~P[i]的前缀字符串中最长的相等前后缀的长度（也就是相等前后缀的最后一个字符在P中的下标位置），具体实现过程可以参考经典的KMP算法的实现方法。KMP函数用于在文本字符串T中查找模式字符串P的出现位置，时间复杂度为O(n+m)，其中n和m分别是T和P的长度。具体实现过程是通过状态转移机制，在遍历文本字符串T的过程中，利用next数组对模式字符串P进行匹配，当模式字符串P匹配成功时，输出模式字符串在文本字符串T中出现的位置，并通过next数组将匹配位置前移。