KMP模式匹配 一（串）求子串的 next 值，用 next 数组存放，全部输出。输入abaabcac

好的，下面是示例代码（C++实现）：

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

using namespace std;

void getNext(string pattern, vector<int>& next) {
    int n = pattern.size();
    next.resize(n);
    next[0] = -1;
    int i = 0, j = -1;
    while (i < n - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int main() {
    string pattern = "abaabcac";
    vector<int> next;
    getNext(pattern, next);
    for (int i = 0; i < next.size(); i++) {
        cout << next[i] << " ";
    }
    cout << endl;
    return 0;
}

输出结果为：

-1 0 0 1 1 2 0 1

其中，next数组的每个元素表示当前字符之前的子串中，最长的既是前缀又是后缀的长度。第一个元素为-1，表示不存在既是前缀又是后缀的子串。