KMP自动机例题(待学习)

KMP自动机可以在O(1)的时间内计算kmp。

KMP自动机数组kmp_auto[i][j]可以表示第i位为'a'+j时的最长前缀长度（此前缀可以包含自身）。

kmp[i]数组，表示第i位的最长前缀长度（不含自身）

可以有kmp[i]=kmp_auto[kmp[i-1]][str[i]-'a'];

例题：

https://codeforces.com/contest/1721/problem/E

题解：

https://www.bilibili.com/video/BV1Zd4y137qa?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=75ae018f8d1181302d7ea76b60c928f4

代码：

官方：https://codeforces.com/blog/entry/106416

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;

int kmp[1000020];
int kmp_auto[1000020][26];
void KMP(string& str)
{
    int n = str.size();
    kmp[0] = 0;
    for (int i = 1; i < n; i++)
    {
        int j = kmp[i - 1];
        while (j > 0 && str[i] != str[j])
            j = kmp[j - 1];
        if (str[i] == str[j]) j++;
        kmp[i] = j;
    }

}
void YD()
{
    string str; cin >> str;
    KMP(str);
    int n = str.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            if (i > 0 && j != str[i] - 'a')
                kmp_auto[i][j] = kmp_auto[kmp[i - 1]][j];
            else
                kmp_auto[i][j] = i + (j == str[i] - 'a');
        }
    }
    int q; cin >> q;
    vector<vector<int>> ans(q);
    while (q--)
    {
        string t; cin >> t;
        int m = t.size();
        str += t;
        for (int i = n; i < m + n; i++)
        {
            for (int j = 0; j < 26; j++)
            {
                if (j != str[i] - 'a')
                    kmp_auto[i][j] = kmp_auto[kmp[i - 1]][j];
                else
                    kmp_auto[i][j] = i + 1;
            }
            kmp[i] = kmp_auto[kmp[i-1]][str[i]-'a'];
            ans[q].push_back(kmp[i]);
        }
        while (m--) str.pop_back();
    }
    q=ans.size();
    for (int i = q - 1; i >= 0; i--)
    {
        for (auto res : ans[i])
        {
            cout << res << ' ';
        }
        cout << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--)
    {
        YD();
    }
    return 0;
}