CF 963D Frequency of String

题目描述

https://codeforces.com/problemset/problem/963/D

简要题意：给定一个长度为 $n$ 的字符串 $S$，现在有 $m$ 次询问，每次询问规定一个整数 $k_i$ 和一个字符串 $T_i$，对于每次询问要求找到一个字符串 $B$ 满足 $B$ 是 $S$ 的子串，且 $T_i$ 在 $B$ 中至少出现了 $k_i$ 次，保证每次询问的 $T_i$ 不同

$|S|,n,\sum |T|\le 10^5$

Solution

首先我们有一个经典结论，对于一个长度为 $n$ 的字符串 $S$ 和 $m$ 个长度和为 $O(n)$ 的字符串 $T_i$，这 $m$ 个字符串在 $S$ 中出现的总次数为 $O(n\sqrt n)$

那么我们只需要能快速求出，每个字符串在 $S$ 中所有出现位置，然后暴力枚举每个出现位置即可，求出现位置可以使用 $bitset$，同时 $bitset$ 有一个函数可以实现 $O(\frac{n}{w}+c)$ 找出所有的 $1$

时间复杂度 $O(\frac{n^2}{w}+n\sqrt n)$

#include <iostream>
#include <bitset>
#include <cstring>
#include <vector>
#define maxn 100010
#define ch(c) (c - 'a')
using namespace std;

int n, m;
char s[maxn], c[maxn];

const int N = 100000;
bitset<N + 1> B[26], ans;

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

    cin >> s + 1 >> m; n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) B[ch(s[i])].set(i); 
    while (m--) {
        int x, l; cin >> x >> c + 1; 
        vector<int> vec; l = strlen(c + 1); ans.set(); int res = n + 1;
        for (int i = l; i; --i) ans &= B[ch(c[i])], i > 1 && (ans >>= 1, 0);
        for (int p = ans._Find_first(); p <= N; p = ans._Find_next(p)) vec.push_back(p);
        for (int i = 0; i + x - 1 < vec.size(); ++i)
            res = min(res, vec[i + x - 1] - vec[i] + 1 + l - 1);
        cout << (res > n ? -1 : res) << "\n";
    }
    return 0;
}