很详细的KMP算法

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，用于在文本串中查找模式串的出现位置。KMP算法的核心是利用已经匹配的部分，尽可能减少无效的比较次数，从而提高匹配的效率。

算法步骤：

预处理模式串的next数组

next数组记录的是模式串中每个前缀的最长相等前缀后缀的长度。例如，对于模式串"abcabcabc"，它的next数组为[0,0,0,1,2,3,4,5,6]。next数组的计算过程如下：

初始化next[0] = -1，next[1] = 0。
令k = 0，j = 1。当j < m时，执行以下操作：
若p[k] == p[j]，则令next[j+1] = k+1，k = k+1，j = j+1；
若k == -1或p[k] != p[j]，则令next[j+1] = 0，j = j+1。

在文本串中查找模式串

在文本串中从左到右遍历每个字符，同时维护一个指向模式串的指针i和一个指向文本串的指针j。若当前字符匹配成功，则i和j分别向右移动一位。若当前字符匹配失败，则根据next数组将i指针向右移动到尽可能少的位置，同时j指针不动，继续尝试匹配下一个字符。

算法实现：

下面是KMP算法的C++实现代码：

vector<int> getNext(string s) {
    int n = s.length();
    vector<int> next(n+1, 0);
    int k = -1, j = 0;
    next[0] = -1;
    while (j < n) {
        if (k == -1 || s[k] == s[j]) {
            k++;
            j++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return next;
}

vector<int> kmp(string s, string p) {
    int n = s.length(), m = p.length();
    vector<int> next = getNext(p);
    vector<int> ans;
    int i = 0, j = 0;
    while (i < n) {
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
            if (j == m) {
                ans.push_back(i-m);
                j = next[j];
            }
        } else {
            j = next[j];
        }
    }
    return ans;
}

其中getNext函数用于预处理模式串的next数组，kmp函数用于在文本串中查找模式串。两个函数的时间复杂度均为O(n+m)，其中n为文本串长度，m为模式串长度