Z 函数模板

发表于 2022-10-31 分类于 OI
本文字数： 719 阅读时长 ≈ 1 分钟

标签：模板 Z函数

扩展 KMP 。将所有后缀和一个串匹配。

查看代码

void init ()
{
    for (int i = 1, t = 0; i < m; ++i)
    {
        if (t + f[t] > i) f[i] = min(f[i - t], t + f[t] - i);
        while (i + f[i] < m && B[f[i]] == B[i + f[i]]) ++f[i];
        if (i + f[i] > t + f[t]) t = i;
    }
    f[0] = m;
}
void match ()
{
    init();
    for (int i = 1, t = 0; i < n; ++i)
    {
        if (t + g[t] > i) g[i] = min(f[i - t], t + g[t] - i);
        while (g[i] < m && i + g[i] < n && B[g[i]] == A[i + g[i]]) ++g[i];
        if (i + g[i] > t + g[t]) t = i;
    }
    while (g[0] < n && g[0] < m && A[g[0]] == B[g[0]]) ++g[0];
}