注意到每次询问串长度都是给定的,并且询问串长(k*)询问次数(q<10^5),所以这里面一个东西大的时候另一个东西就小,那么考虑对较小的下功夫
如果(kle sqrt{n}),那么可以(O(k^2))暴力枚举询问串的每一个子串,然后在(S)的sam找到这个子串对应的点,算出出现次数,并且乘上在区间([a,b])中这个子串询问的出现次数.找到子串对应的点为了方便,可以依次让询问串的某个前缀在sam上匹配,然后按长度从大到小枚举前缀的后缀,从匹配位置开始倍增跳父亲,直到当前点包含的串的长度区间包含当前长度;然后子串在区间([a,b])询问次数可以主席树(雾).所以这部分复杂度是(O(qk^2logn)=O(nsqrt{n}logn))
如果(k> sqrt{n}),那么(qle sqrt{n}),所以可以枚举(m)个询问区间对应的子串,分别算答案.具体实现可以参考上面,依次用前缀在sam上匹配,然后处理右端点为当前位置的询问子串贡献.这部分是(O(qmlogn)=O(nsqrt{n}logn))
然后不知道为什么我的倍增被卡了...应该是我写丑了吧qwq.然后改成暴力跳父亲就跑的飞快
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double
using namespace std;
const int N=1e5+10;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,m,q,kk,lz;
char cc[N],ss[N];
struct SAM
{
int fa[N<<1][19],len[N<<1],ch[N<<1][26],sz[N<<1],la,tt;
vector<int> e[N<<1];
SAM(){la=tt=1;}
void extd(int cx)
{
int np=++tt,p=la;
len[np]=len[p]+1,sz[np]=1,la=tt;
while(!ch[p][cx]) ch[p][cx]=np,p=fa[p][0];
if(!p) fa[np][0]=1;
else
{
int q=ch[p][cx];
if(len[q]==len[p]+1) fa[np][0]=q;
else
{
int nq=++tt;
fa[nq][0]=fa[q][0],len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(int)*26);
fa[np][0]=fa[q][0]=nq;
while(ch[p][cx]==q) ch[p][cx]=nq,p=fa[p][0];
}
}
}
void dfs(int x)
{
for(int j=1;j<=lz;++j)
{
fa[x][j]=fa[fa[x][j-1]][j-1];
if(!fa[x][j]) break;
}
vector<int>::iterator it;
for(it=e[x].begin();it!=e[x].end();++it)
{
int y=*it;
dfs(y),sz[x]+=sz[y];
}
}
void inii()
{
for(int i=2;i<=tt;++i) e[fa[i][0]].push_back(i);
dfs(1);
}
}sam;
namespace ct1
{
int id[320][320],tti;
int s[N*20],ch[N*20][2],rt[N],tt;
void inst(int o1,int o2,int x)
{
int l=1,r=tti;
s[o1]=s[o2]+1;
while(l<r)
{
int mid=(l+r)>>1;
if(x<=mid)
{
ch[o1][0]=++tt,ch[o1][1]=ch[o2][1];
o1=ch[o1][0],o2=ch[o2][0];
r=mid;
}
else
{
ch[o1][0]=ch[o2][0],ch[o1][1]=++tt;
o1=ch[o1][1],o2=ch[o2][1];
l=mid+1;
}
s[o1]=s[o2]+1;
}
}
int quer(int o1,int o2,int l,int r,int lx)
{
if(!s[o1]) return 0;
if(l==r) return s[o1]-s[o2];
int mid=(l+r)>>1;
if(lx<=mid) return quer(ch[o1][0],ch[o2][0],l,mid,lx);
else return quer(ch[o1][1],ch[o2][1],mid+1,r,lx);
}
void wk()
{
for(int i=1;i<=kk;++i)
for(int j=i;j<=kk;++j)
id[i][j]=++tti;
for(int i=1;i<=m;++i)
{
int l=rd()+1,r=rd()+1;
inst(rt[i]=++tt,rt[i-1],id[l][r]);
}
while(q--)
{
scanf("%s",ss+1);
int a=rd()+1,b=rd()+1;
LL ans=0;
for(int i=1,p=1,ll=0;i<=kk;++i)
{
while(p>1&&!sam.ch[p][ss[i]-'a']) p=sam.fa[p][0],ll=sam.len[p];
if(sam.ch[p][ss[i]-'a'])
{
p=sam.ch[p][ss[i]-'a'],++ll;
int x=p,nm;
for(int j=i-ll+1;j<=i;++j)
if((nm=quer(rt[b],rt[a-1],1,tti,id[j][i])))
{
if(sam.len[sam.fa[x][0]]+1>i-j+1)
{
for(int k=lz;~k;--k)
if(sam.len[sam.fa[sam.fa[x][k]][0]]+1>i-j+1)
x=sam.fa[x][k];
x=sam.fa[x][0];
}
ans+=1ll*sam.sz[x]*nm;
}
}
else p=1,ll=0;
}
printf("%lld
",ans);
}
}
}
namespace ct2
{
struct node
{
int l,i;
bool operator < (const node &bb) const {return l<bb.l;}
};
vector<node> qr[N];
void wk()
{
for(int i=1;i<=m;++i)
{
int l=rd()+1,r=rd()+1;
qr[r].push_back((node){l,i});
}
for(int i=1;i<=n;++i) sort(qr[i].begin(),qr[i].end());
while(q--)
{
scanf("%s",ss+1);
int a=rd()+1,b=rd()+1;
LL ans=0;
for(int i=1,p=1,ll=0;i<=kk;++i)
{
while(p>1&&!sam.ch[p][ss[i]-'a']) p=sam.fa[p][0],ll=sam.len[p];
if(sam.ch[p][ss[i]-'a'])
{
p=sam.ch[p][ss[i]-'a'],++ll;
int x=p;
vector<node>::iterator it;
for(it=qr[i].begin();it!=qr[i].end();++it)
{
int j=(*it).l,ii=(*it).i;
if(i-j+1<=ll&&ii>=a&&ii<=b)
{
/*if(sam.len[sam.fa[x][0]]+1>i-j+1)
{
for(int k=lz;~k;--k)
if(sam.len[sam.fa[sam.fa[x][k]][0]]+1>i-j+1)
x=sam.fa[x][k];
x=sam.fa[x][0];
}*/
while(sam.len[sam.fa[x][0]]+1>i-j+1) x=sam.fa[x][0];
ans+=sam.sz[x];
}
}
}
else p=1,ll=0;
}
printf("%lld
",ans);
}
}
}
int main()
{
n=rd(),m=rd(),q=rd(),kk=rd();
scanf("%s",cc+1);
for(int i=1;i<=n;++i) sam.extd(cc[i]-'a');
lz=log2(n),sam.inii();
if(kk<=315) ct1::wk();
else ct2::wk();
return 0;
}