ababc 的 next 表

一段文本 abababcababcabababc（19 个字符，下标从 0 起）和一个模式 ababc。

把模式的 next 表算出来：

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

const string T = "abababcababcabababc";
const string P = "ababc";

vector<int> build_next(const string& p) {
    vector<int> f(p.size(), 0);
    int k = 0;
    for (int i = 1; i < (int)p.size(); i++) {
        while (k > 0 && p[i] != p[k]) k = f[k - 1];
        if (p[i] == p[k]) k++;
        f[i] = k;
    }
    return f;
}

string join(const vector<int>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? "/" : "") + to_string(v[i]);
    return s;
}

int main() {
    cout << join(build_next(P)) << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）