Description
Solution
当 \(k\) 值较小时,发现询问串比较多,串长比较小
然后对 \(Q\) 个询问区间离线跑莫队,一次考虑每一个区间的贡献
假设一个区间 \([i,j]\) 出现的次数是 \(c[i][j]\),然后 \(O(k^2)\) 求出每一个区间的贡献,乘上 \(c[i][j]\) 就是答案
当 \(k\) 值较大时,询问次数比较少,串长比较大
考虑与询问次数有关的做法
对于每一个询问,预处理出 \(w\) 的每一个前缀在 \(S\) 的 \(SAM\) 中匹配到的位置和匹配的长度
右端点固定时,左端点移动形成的串就是这个右端点对应的前缀的后缀,每一次跳父亲就可以跳到
倍增到合法长度的节点即可
显然 \(k\) 取 \(\sqrt{10^5}\) 时最优
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void gi(T &x){
int f;char c;
for (f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for (x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}
const int N=2e5+10,M=320,B=20;
int n,m,Q,K,ch[N][26],fa[N],cur=1,cnt=1,len[N],sz[N],sa[N],c[N],g[N];
char s[N];
inline void ins(int c){
int p=cur;cur=++cnt;len[cur]=len[p]+1;
for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;
if(!p)fa[cur]=1;
else{
int q=ch[p][c];
if(len[p]+1==len[q])fa[cur]=q;
else{
int nt=++cnt;len[nt]=len[p]+1;
memcpy(ch[nt],ch[q],sizeof(ch[q]));
fa[nt]=fa[q];fa[q]=fa[cur]=nt;
for(;p && ch[p][c]==q;p=fa[p])ch[p][c]=nt;
}
}sz[cur]=1;
}
inline void priwork(){
for(int i=1;i<=cnt;i++)c[len[i]]++;
for(int i=1;i<=n;i++)c[i]+=c[i-1];
for(int i=cnt;i>=1;i--)sa[c[len[i]]--]=i;
for(int i=cnt;i>=1;i--)sz[fa[sa[i]]]+=sz[sa[i]];
}
struct D{int l,r;}e[N];
struct data{int l,r,id;}q[N];
inline bool comp(data i,data j){return i.l/B!=j.l/B?i.l/B<j.l/B:i.r<j.r;}
namespace solo{
char w[N][M];int v[M][M];ll ans[N];
inline void add(int x){v[e[x].l][e[x].r]++;}
inline void del(int x){v[e[x].l][e[x].r]--;}
inline ll solve(int x){
int len=strlen(w[x]+1),p,c;ll ret=0;
for(int i=1;i<=len;i++){
p=1;
for(int j=i;j<=len;j++){
c=w[x][j]-'a';
if(!ch[p][c])break;
p=ch[p][c];
ret+=v[i][j]*sz[p];
}
}
return ret;
}
void main(){
for(int i=1;i<=Q;i++){
scanf("%s",w[i]+1);
gi(q[i].l);gi(q[i].r);q[i].id=i;q[i].l++;q[i].r++;
}
sort(q+1,q+Q+1,comp);
int l=1,r=0;
for(int i=1;i<=Q;i++){
while(r<q[i].r)add(++r);
while(l>q[i].l)add(--l);
while(r>q[i].r)del(r--);
while(l<q[i].l)del(l++);
ans[q[i].id]=solve(q[i].id);
}
for(int i=1;i<=Q;i++)printf("%lld\n",ans[i]);
}
}
namespace sol{
char w[N];int pos[N],f[N][20];
inline int qry(int x,int y){
if(len[x]<y)return 0;
for(int i=19;i>=0;i--)
if(f[x][i] && len[f[x][i]]>=y)x=f[x][i];
return sz[x];
}
void main(){
int x,y,le,p,now;
for(int i=1;i<=cnt;i++)f[i][0]=fa[i];
for(int j=1;j<20;j++)
for(int i=1;i<=cnt;i++)f[i][j]=f[f[i][j-1]][j-1];
for(int i=1;i<=Q;i++){
scanf("%s",w+1);le=strlen(w+1);
p=1;now=0;
for(int j=1;j<=le;j++){
int c=w[j]-'a';
if(ch[p][c])p=ch[p][c],now++;
else{
while(p>1 && !ch[p][c])p=fa[p];
if(ch[p][c])now=len[p]+1,p=ch[p][c];
else now=0;
}
pos[j]=p;g[j]=now;
}
gi(x);gi(y);x++;y++;
ll ret=0;
for(int j=x;j<=y;j++)
if(g[e[j].r]>=e[j].r-e[j].l+1)
ret+=qry(pos[e[j].r],e[j].r-e[j].l+1);
printf("%lld\n",ret);
}
}
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
cin>>n>>m>>Q>>K;
scanf("%s",s+1);
for(int i=1;i<=n;i++)ins(s[i]-'a');
priwork();
for(int i=1;i<=m;i++)gi(e[i].l),gi(e[i].r),e[i].l++,e[i].r++;
if(K<M)solo::main();
else sol::main();
return 0;
}