http://codeforces.com/contest/963/problem/D
题解：https://www.cnblogs.com/Blue233333/p/8881614.html
记M为n个串的总长，L为s的长度
询问串的不同的长度只会有sqrt(M)级别个
（最差的情况是串长为1,2,3,...,x，此时M=(x+1)x/2，因此x是sqrt(M)级别的）
s的子串中，长度为特定值k的子串个数是L级别的，
由于各个字符串互不相同，这就相当于n个串中所有长度为k的串，分别计算出它们在s中出现次数，各个计算结果的和是L级别的
因此只要设计对于每一个询问串都是O(串长+出现次数)的算法就行了
花了好长时间写了个后缀自动机字符串匹配啊。。。。莫不是搞复杂了
代码1.（using连用多个是c++17的，曾经还CE了）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
using namespace std;
typedef long long LL;
char s[],ss[];
int ll,x[],l2;
int pp[];
vector<int> vv[];
set<int> sss[];
int n,ans[];
int lll[];
namespace SAM
{
int mem,np,root;
int len[],par[];
int trans[][];
int posl[],posr[];
void append(int ch)
{
int p=np;np=++mem;len[np]=len[p]+;
for(;p&&!trans[p][ch];p=par[p]) trans[p][ch]=np;
if(!p) par[np]=root;
else
{
int q=trans[p][ch];
if(len[q]==len[p]+) par[np]=q;
else
{
int nq=++mem;par[nq]=par[q];par[q]=par[np]=nq;
memcpy(trans[nq],trans[q],sizeof(trans[nq]));len[nq]=len[p]+;
for(;p&&trans[p][ch]==q;p=par[p]) trans[p][ch]=nq;
}
}
}
void build()
{
np=root=++mem;
int i,now;
for(i=;i<=ll;i++) append(s[i]-'a'),pp[i]=np,sss[np].insert(i);
for(i=;i<=ll;i++)
{
for(now=pp[i];now!=root&&!posr[now]&&!posl[now];now=par[now])
{
posl[now]=i-len[par[now]];posr[now]=i-len[now]+;
}
}
}
}
namespace ST
{
int ch[][];
using SAM::par;
void build()
{
int i;
for(i=;i<=SAM::mem;i++)
{
if(par[i])
{
ch[par[i]][s[SAM::posl[i]]-'a']=i;
}
}
}
/*
void out()
{
int i,j,k;using SAM::len,SAM::posl,SAM::posr;
for(i=1;i<=SAM::mem;i++)
{
for(j=0;j<26;j++)
{
if(ch[i][j])
{
printf("%d %d ",i,ch[i][j]);
for(k=posl[ch[i][j]];k>=posr[ch[i][j]];k--) putchar(s[k]);
puts("");
}
}
}
}
*/
}
void work(int tt)
{
using SAM::root,SAM::posl,SAM::posr,ST::ch;
int i,now=root,j,k;
for(i=l2;i>=;)
{
now=ch[now][ss[i]-'a'];
if(!now) return;
for(j=i,k=posl[now];j>=&&k>=posr[now];j--,k--)
if(ss[j]!=s[k])
return;
i-=posl[now]-posr[now]+;
//printf("b%d %d %d %d\n",now,i,posl[now],posr[now]);
}
vv[now].push_back(tt);//printf("a%d\n",now);
}
queue<int> q;int in[];
void work2()
{
using SAM::mem,SAM::par;
int i,j,t,l,r;vector<int> tmp;
for(i=;i<=mem;i++) if(par[i]) in[par[i]]++;
for(i=;i<=mem;i++) if(!in[i]) q.push(i);
while(!q.empty())
{
t=q.front();q.pop();
if(vv[t].size())
{
tmp.clear();
for(auto k:sss[t]) tmp.push_back(k);
//for(i=0;i<tmp.size();i++) printf("%d ",tmp[i]);puts("");
}
for(auto p:vv[t])
{
for(i=,j=x[p]-;j<tmp.size();i++,j++)
{
ans[p]=min(ans[p],tmp[j]-tmp[i]+lll[p]);
}
}
if(par[t])
{
if(sss[par[t]].size()<sss[t].size()) swap(sss[par[t]],sss[t]);
for(auto k:sss[t]) sss[par[t]].insert(k);
sss[t].clear();
in[par[t]]--;
if(!in[par[t]]) q.push(par[t]);
}
}
}
int main()
{
int i;
scanf("%s",s+);ll=strlen(s+);
SAM::build();ST::build();
//ST::out();return 0;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d%s",&x[i],ss+);l2=lll[i]=strlen(ss+);
work(i);
}
memset(ans,0x3f,sizeof(ans));
work2();
for(i=;i<=n;i++)
printf("%d\n",ans[i]==0x3f3f3f3f?-:ans[i]);
return ;
}
代码2:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
using namespace std;
typedef long long LL;
char s[],ss[];
int ll,x[],l2;
int pp[];
vector<int> vv[];
set<int> sss[];
int n,ans[];
int lll[];
namespace SAM
{
int mem,np,root;
int len[],par[];
int trans[][];
int posl[],posr[];
void append(int ch)
{
int p=np;np=++mem;len[np]=len[p]+;
for(;p&&!trans[p][ch];p=par[p]) trans[p][ch]=np;
if(!p) par[np]=root;
else
{
int q=trans[p][ch];
if(len[q]==len[p]+) par[np]=q;
else
{
int nq=++mem;par[nq]=par[q];par[q]=par[np]=nq;
memcpy(trans[nq],trans[q],sizeof(trans[nq]));len[nq]=len[p]+;
posl[nq]=posl[q];posr[nq]=posl[q]-(len[nq]-len[par[nq]])+;posl[q]=posr[nq]-;
for(;p&&trans[p][ch]==q;p=par[p]) trans[p][ch]=nq;
}
}
}
void build()
{
np=root=++mem;
int i,now;
for(i=;i<=ll;i++)
{
append(s[i]-'a'),sss[np].insert(i);
for(now=np;now!=root&&!posr[now]&&!posl[now];now=par[now])
{
posl[now]=i-len[par[now]];posr[now]=i-len[now]+;
}
}
}
}
namespace ST
{
int ch[][];
using SAM::par;
void build()
{
int i;
for(i=;i<=SAM::mem;i++)
{
if(par[i])
{
ch[par[i]][s[SAM::posl[i]]-'a']=i;
}
}
}
/*
void out()
{
int i,j,k;using SAM::len,SAM::posl,SAM::posr;
for(i=1;i<=SAM::mem;i++)
{
for(j=0;j<26;j++)
{
if(ch[i][j])
{
printf("%d %d ",i,ch[i][j]);
for(k=posl[ch[i][j]];k>=posr[ch[i][j]];k--) putchar(s[k]);
puts("");
}
}
}
}
*/
}
void work(int tt)
{
using SAM::root,SAM::posl,SAM::posr,ST::ch;
int i,now=root,j,k;
for(i=l2;i>=;)
{
now=ch[now][ss[i]-'a'];
if(!now) return;
for(j=i,k=posl[now];j>=&&k>=posr[now];j--,k--)
if(ss[j]!=s[k])
return;
i-=posl[now]-posr[now]+;
//printf("b%d %d %d %d\n",now,i,posl[now],posr[now]);
}
vv[now].push_back(tt);//printf("a%d\n",now);
}
queue<int> q;int in[];
void work2()
{
using SAM::mem,SAM::par;
int i,j,t;vector<int> tmp;
for(i=;i<=mem;i++) if(par[i]) in[par[i]]++;
for(i=;i<=mem;i++) if(!in[i]) q.push(i);
while(!q.empty())
{
t=q.front();q.pop();
if(vv[t].size())
{
tmp.clear();
for(auto k:sss[t]) tmp.push_back(k);
//for(i=0;i<tmp.size();i++) printf("%d ",tmp[i]);puts("");
}
for(auto p:vv[t])
{
for(i=,j=x[p]-;j<tmp.size();i++,j++)
{
ans[p]=min(ans[p],tmp[j]-tmp[i]+lll[p]);
}
}
if(par[t])
{
if(sss[par[t]].size()<sss[t].size()) swap(sss[par[t]],sss[t]);
for(auto k:sss[t]) sss[par[t]].insert(k);
sss[t].clear();
in[par[t]]--;
if(!in[par[t]]) q.push(par[t]);
}
}
}
int main()
{
int i;
scanf("%s",s+);ll=strlen(s+);
SAM::build();ST::build();
//ST::out();return 0;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d%s",&x[i],ss+);l2=lll[i]=strlen(ss+);
work(i);
}
memset(ans,0x3f,sizeof(ans));
work2();
for(i=;i<=n;i++)
printf("%d\n",ans[i]==0x3f3f3f3f?-:ans[i]);
return ;
}
还有一份看上去很高妙的bitset字符串匹配（不是自己写的，先记一下）
来源：http://codeforces.com/contest/963/submission/37784765
#include<bits/stdc++.h>
#define N 100005
using namespace std;
bitset<N> b[],tmp;
char s[N],t[N];
int main(){
scanf("%s",s);
int n=strlen(s);
for (int i=;i<n;i++)
b[s[i]-'a'][i]=;
int Q; scanf("%d",&Q);
while (Q--){
int k; scanf("%d%s",&k,t);
int m=strlen(t);
tmp.set();
for (int i=;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=;i+k-<v.size();i++)
ans=min(ans,v[i+k-]-v[i]+m);
printf("%d\n",ans);
}
}
就是搞复杂了。。
要找一个字符串，只要在后缀自动机上一位一位找过去，保证最后到达的一定也是后缀树上的对应节点。。。
#pragma GCC diagnostic error "-std=c++11"
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
using namespace std;
typedef long long LL;
char s[],ss[];
int ll,x[],l2;
int pp[];
vector<int> vv[];
set<int> sss[];
int n,ans[];
int lll[];
int teststet;
int ssss; namespace SAM
{
int mem,np,root;
int len[],par[];
int trans[][];
void append(int ch)
{
int p=np;np=++mem;len[np]=len[p]+;
for(;p&&!trans[p][ch];p=par[p]) trans[p][ch]=np;
if(!p) par[np]=root;
else
{
int q=trans[p][ch];
if(len[q]==len[p]+) par[np]=q;
else
{
int nq=++mem;par[nq]=par[q];par[q]=par[np]=nq;
memcpy(trans[nq],trans[q],sizeof(trans[nq]));len[nq]=len[p]+;
for(;p&&trans[p][ch]==q;p=par[p]) trans[p][ch]=nq;
}
}
}
void build()
{
np=root=++mem;
int i;
for(i=;i<=ll;i++)
{
append(s[i]-'a'),sss[np].insert(i);
}
}
}
void work(int tt)
{
using SAM::trans;
int i,now=SAM::root;
for(i=;i<=l2;i++)
{
now=trans[now][ss[i]-'a'];
}
vv[now].push_back(tt);
}
queue<int> q;int in[];
void work2()
{
using SAM::mem;using SAM::par;
int i,j,t;vector<int> tmp;
for(i=;i<=mem;i++) if(par[i]) in[par[i]]++;
for(i=;i<=mem;i++) if(!in[i]) q.push(i);
while(!q.empty())
{
t=q.front();q.pop();
if(vv[t].size())
{
tmp.clear();
for(auto k:sss[t]) tmp.push_back(k);
}
for(auto p:vv[t])
{
for(i=,j=x[p]-;j<tmp.size();i++,j++)
{
ans[p]=min(ans[p],tmp[j]-tmp[i]+lll[p]);
}
}
if(par[t])
{
if(sss[par[t]].size()<sss[t].size()) swap(sss[par[t]],sss[t]);
for(auto k:sss[t]) sss[par[t]].insert(k);
sss[t].clear();
in[par[t]]--;
if(!in[par[t]]) q.push(par[t]);
}
}
}
int main()
{
int i;
scanf("%s",s+);ll=strlen(s+);
SAM::build();
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d%s",&x[i],ss+);l2=lll[i]=strlen(ss+);
work(i);
}
int aefsaf;
memset(ans,0x3f,sizeof(ans));
work2();
for(i=;i<=n;i++)
printf("%d\n",ans[i]==0x3f3f3f3f?-:ans[i]);
return ;
}