CodeForces - 963D：Frequency of String （bitset暴力搞）

You are given a string?ss. You should answer?nn?queries. The?ii-th query consists of integer?kiki?and string?mimi. The answer for this query is the minimum length of such a string?tt?that?tt?is a substring of?ss?and?mimi?has at least?kiki?occurrences as a substring in?tt.

A substring of a string is a continuous segment of characters of the string.

It is guaranteed that for any two queries the strings?mimi?from these queries are different.

Input

The first line contains string?ss?(1≤|s|≤105)(1≤|s|≤105).

The second line contains an integer?nn?(1≤n≤1051≤n≤105).

Each of next?nn?lines contains an integer?kiki?(1≤ki≤|s|)(1≤ki≤|s|)?and a non-empty string?mimi?— parameters of the query with number?ii,in this order.

All strings in input consists of lowercase English letters. Sum of length of all strings in input doesn‘t exceed?105105. All?mimi?are distinct.

Output

For each query output the answer for it in a separate line.

If a string?mimi?occurs in?ss?less that?kiki?times,output?-1.

Examples

aaaaa
5
3 a
3 aa
2 aaa
3 aaaa
1 aaaaa

3
4
4
-1
5

abbb
7
4 b
1 ab
3 bb
1 abb
2 bbb
1 a
2 abbb

-1
2
-1
3
-1
1
-1

题意：给定串S，N次询问，每次求最短的子串，使得s出现次数等于k。

思路：后缀自动机，AC自动机，hash都可以做；bitset，然后尺取法。有点暴力，不过CF跑得过去。

思路2：考虑到串的长度种类不超过NsqrtN种，我们可以把这些sqrtN种长度的hash都保存起来，以hash值维第一关键字，以坐标为第二关键字，排序。然后对于每个询问，我们lower_bound到这一类hash值的位置，然后尺取法得到最小答案。

关键还是要回函数bitset._Find_first()，和bitset._Find_next(i)

#include<bits/stdc++.h>
#define N 100005
using namespace std;
char s[N],t[N];
bitset<N>b[26],tmp;
int main(){
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;i++)
        b[s[i]-‘a‘][i]=1;
    int Q; scanf("%d",&Q);
    while (Q--){
        int k; scanf("%d%s",&k,t);
        int m=strlen(t);
        tmp.set();
        for(int i=0;i<m;i++) tmp&=b[t[i]-‘a‘]>>i;
        if (tmp.count()<k){ puts("-1"); continue;}
        vector<int> v;
        for(int i=tmp._Find_first();i<n;i=tmp._Find_next(i))
            v.push_back(i);
        int ans=1e9;
        for (int i=0;i+k-1<v.size();i++)
            ans=min(ans,v[i+k-1]-v[i]+m);
        printf("%dn",ans);
    }
    return 0;
}