Tinkoff Internship Warmup Round 2018 and Codeforces Round 475 (Div. 1) D. Frequency of String

Problem - D - Codeforces

题意

给定一个字符串，n次询问，每次询问一个字符串在给定字符串的子串中出现k次时子串的最小长度

分析

多模式匹配，想到使用AC自动机，由于询问子串总长度不超过M = 1E5，那么对于长度不同的串最多有$\sqrt{M}$，那么我们队fail树中最长的链长度小于$\sqrt{M}$，对原串中的每个位置直接沿着fail指针向上传递，则共传递n$\sqrt{M}$次，最后对每次询问统计答案

#include <bits/stdc++.h>

using i64 = long long;

struct ACA
{
    std::vector<std::array<int, 26>> tr;
    std::vector<int> ne;
    std::vector<int> len;
    std::vector<int> invid;
    std::vector<int> cnt;
    std::vector<int> q;
    std::vector<std::vector<int>> adj;
    std::vector<std::pair<int, int>> que;
    int idx;

    ACA(int n) : tr(n + 1), ne(n + 1), invid(n + 1), len(n + 1), cnt(n + 1), q(n + 1), que(n + 1)
    {
        adj.assign(n + 1, std::vector<int>());
        idx = 0;
    }

    void insert(std::string s, int x, int k)
    {
        int p = 0;
        int sz = s.size();
        for (int i = 0; i < sz; i++)
        {
            int t = s[i] - 'a';
            if (!tr[p][t])
                tr[p][t] = ++idx;
            p = tr[p][t];
        }
        len[p] = s.size();
        que[p] = {k, x};
        invid[x] = p;
    }

    void build()
    {
        int hh = 0, tt = -1;
        for (int i = 0; i < 26; i++)
            if (tr[0][i])
                q[++tt] = tr[0][i];
        while (hh <= tt)
        {
            int p = q[hh++];
            adj[ne[p]].push_back(p);
            for (int i = 0; i < 26; i++)
                if (!tr[p][i])
                    tr[p][i] = tr[ne[p]][i];
                else
                {
                    ne[tr[p][i]] = tr[ne[p]][i];
                    q[++tt] = tr[p][i];
                }
        }
    }

    void query(std::string str)
    {
        int sz = str.size();
        for (int i = 0, now = 0; i < sz; i++)
        {
            int t = str[i] - 'a';
            now = tr[now][t];
            int p = now;
            cnt[p]++; // 对应的节点加一，在最后bfs是保证前节点全部加一
        }
    }

    void dfs(int u)
    {
        for (auto v : adj[u])
        {
            dfs(v);
            cnt[u] += cnt[v];
        }
    }
};

constexpr int N = 1E5;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string str;
    std::cin >> str;
    ACA aca(N);
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int k;
        std::string s;
        std::cin >> k >> s;
        aca.insert(s, i, k);
    }

    aca.build();
    std::vector<int> up(N + 1);
    auto dfs1 = [&](auto self, int u, int last) -> void
    {
        up[u] = last;
        if (aca.que[u].second)
            last = u;
        for (auto v : aca.adj[u])
            self(self, v, last);
    };

    std::vector<std::vector<int>> id(n + 1, std::vector<int>());

    dfs1(dfs1, 0, 0);
    int sz = str.size();
    for (int i = 0, now = 0; i < sz; i++)
    {
        int t = str[i] - 'a';
        now = aca.tr[now][t];
        if (aca.que[now].first)
            id[aca.que[now].second].push_back(i);
        int p = up[now];
        while (p)
        {
            id[aca.que[p].second].push_back(i);
            p = up[p];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int invid = aca.invid[i];
        auto [k, z] = aca.que[invid];
        if (id[i].size() < k)
            std::cout << -1 << "\n";
        else
        {
            int res = 1E9;
            for (int j = k - 1; j < id[i].size(); j++)
                res = std::min(res, id[i][j] - id[i][j - k + 1] + aca.len[invid]);
            std::cout << res << "\n";
        }
    }

    return 0;
}