题意:有一个串s,n个串模式串t,问s的子串中长度最小的包含t k次的长度是多少
题解:把所有t建ac自动机,把s在ac自动机上匹配.保存每个模式串在s中出现的位置.这里由于t两两不同最多只有xsqrt(x),x是总长度.然后双指针扫一遍即可
这里有一个很重要的优化技巧,由于ac自动机上不是每个点都是t的结尾,我们把fail向上跳一次变成直接跳到t的结尾,build预处理一下
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define fi first
#define se second
#define db double
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
//#define C 0.5772156649
//#define ls l,m,rt<<1
//#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define ull unsigned long long
//#define base 1000000000000000000
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}
template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const ull ba=233;
const db eps=1e-7;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=100000+10,maxn=100000+10,inf=0x3f3f3f3f;
char s[N],p[N];
vi v[N];
struct ACM{
int root,tot;
int ch[N][26],fail[N],id[N],go[N];
int newnode()
{
memset(ch[tot],-1,sizeof ch[tot]);
id[tot]=0;
return tot++;
}
void init(){tot=0;root=newnode();}
void ins(int x)
{
int now=root,n=strlen(s);
for(int i=0;i<n;i++)
{
if(ch[now][s[i]-'a']==-1)ch[now][s[i]-'a']=newnode();
now=ch[now][s[i]-'a'];
}
id[now]=x;
}
void build()
{
queue<int>q;
fail[root]=root;
for(int i=0;i<26;i++)
{
if(ch[root][i]==-1)ch[root][i]=root;
else
{
fail[ch[root][i]]=root;
q.push(ch[root][i]);
}
}
while(!q.empty())
{
int now=q.front();q.pop();
if(id[fail[now]])go[now]=fail[now];
else go[now]=go[fail[now]];
for(int i=0;i<26;i++)
{
if(ch[now][i]==-1)ch[now][i]=ch[fail[now]][i];
else
{
fail[ch[now][i]]=ch[fail[now]][i];
q.push(ch[now][i]);
}
}
}
}
void cal()
{
int now=root;
for(int i=0;p[i];i++)
{
now=ch[now][p[i]-'a'];
int te=now;
while(te!=root)
{
if(id[te])v[id[te]].pb(i);
te=go[te];
}
}
}
}ac;
int a[N],sz[N];
int main()
{
int n;
scanf("%s%d",p,&n);
ac.init();
for(int i=1;i<=n;i++)
{
scanf("%d%s",&a[i],s);
sz[i]=strlen(s);
ac.ins(i);
}
ac.build();
ac.cal();
for(int i=1;i<=n;i++)
{
if(v[i].size()<a[i])puts("-1");
else
{
// for(int x:v[i])printf("%d ",x);puts("");
int ans=inf;
for(int j=0;j+a[i]-1<v[i].size();j++)
{
ans=min(ans,v[i][j+a[i]-1]-v[i][j]+sz[i]);
}
printf("%d\n",ans);
}
}
return 0;
}
/********************
********************/