题目大意：
给一个串s和很多模式串，对每个模式串求s的一个最短的子串使得这个子串中包含至少k个该模式串。
题目分析：
均摊分析，有sqrt(n)种长度不同的模式串，所以有关的串只有msqrt(n)种。暴力用AC自动机找出来即可。
代码：
#include<bits/stdc++.h>
using namespace std; const int maxn = ;
const int sigma = ; int n,num,root,d[maxn],fa[maxn],fail[maxn],Ex[maxn];
string str,query[maxn];
vector<int> ans[maxn]; int Number(char ch){return (int)(ch-'a');} struct trie{int data,end,nxt[sigma];}T[maxn]; void insert(int now,int pla,int tnode){
if(pla == query[now].size()){T[tnode].end=now;return;}
int p = Number(query[now][pla]);
if(T[tnode].nxt[p]){insert(now,pla+,T[tnode].nxt[p]);}
else{
num++;T[tnode].nxt[p] = num;T[num].data = p;
fa[num] = tnode; insert(now,pla+,num);
}
} void read(){
cin >> str >> n;
for(int i=;i<=n;i++){
cin >> d[i] >> query[i];
insert(i,,root);
}
} queue <int> q;
void BuildAC(){
for(int i=;i<sigma;i++) if(T[root].nxt[i]) q.push(T[root].nxt[i]);
while(!q.empty()){
int k = q.front();q.pop();
int hh = fail[fa[k]];
while(hh != root){
if(T[hh].nxt[T[k].data]){fail[k]=T[hh].nxt[T[k].data];break;}
else hh = fail[hh];
}
if(T[hh].nxt[T[k].data]&&(!fail[k])&&T[hh].nxt[T[k].data]!=k){
fail[k]=T[hh].nxt[T[k].data];
}
for(int i=;i<sigma;i++) if(T[k].nxt[i]) q.push(T[k].nxt[i]);
}
} void BuildExtraFail(){
q.push(root);
while(!q.empty()){
int k = q.front();q.pop();
int hh = fail[k];
if(T[hh].end){Ex[k] = hh;}else Ex[k] = Ex[hh];
for(int i=;i<sigma;i++) if(T[k].nxt[i]) q.push(T[k].nxt[i]);
}
} void RunAC(){
int now = root;
for(int i=;i<str.length();i++){
int p = Number(str[i]);
if(T[now].nxt[p]) now = T[now].nxt[p];
else{
int hh = fail[now];
int fg = false;
while(hh != root){
if(T[hh].nxt[p]){fg=;now=T[hh].nxt[p];break;}
else hh = fail[hh];
}
if(fg == )goto loop;
if(T[hh].nxt[T[p].data])now=T[hh].nxt[T[p].data];
else now = root;
}
loop:int z = Ex[now];
if(T[now].end) ans[T[now].end].push_back(i);
while(z!=root){ans[T[z].end].push_back(i);z=Ex[z];}
}
} int Min(int a,int b){return a<b?a:b;} void work(){
BuildAC();
BuildExtraFail();
RunAC();
for(int i=;i<=n;i++){
if(ans[i].size()<d[i]){cout<<-<<endl;continue;}
int minn = ;
for(int j=d[i]-;j<ans[i].size();j++){
minn = Min(minn,ans[i][j]-ans[i][j-d[i]+]+query[i].length());
}
cout<<minn<<endl;
}
} int main(){
read();
work();
return ;
}