解题思路:
很坑的一道题,需要离线处理,假如只有一组询问,那么就可以直接将endpos集合直接累加输出就好了。
这里就要将询问挂在树节点上,在进行线段树合并时查询就好了。
代码超级容易写挂的。
注意要将匹配串时尽量找到最浅根,易于统计答案。
倍增处理就好了。
代码:
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
const int N=;
struct int_2{
int vl;
int ps;
}imt;
struct sant{
int tranc[];
int len;
int pre;
}s[N];
struct pnt{
int hd;
int fa[];
int rt;
std::vector<int>posquery;
}p[N];
struct ent{
int twd;
int lst;
}e[N];
struct trnt{
int ls;
int rs;
int_2 val;
}tr[N<<];
struct qnt{
int l;
int r;
int pl;
int pr;
int lt;
int pos;
int_2 ans;
void Insert(void)
{
scanf("%d%d%d%d",&l,&r,&pl,&pr);
lt=pr-pl+;
return ;
}
}q[N];
char tmp[N];
char str[N];
std::vector<int>lpnt[N];
int n,m,Q;
int siz;
int fin;
int cnt;
int tnt;
void ade(int f,int t)
{
cnt++;
e[cnt].twd=t;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
int_2 max(int_2 x,int_2 y)
{
if(x.vl!=y.vl)
return x.vl>y.vl?x:y;
return x.ps<y.ps?x:y;
}
void pushup(int spc)
{
tr[spc].val=max(tr[tr[spc].ls].val,tr[tr[spc].rs].val);
return ;
}
void update(int l,int r,int &spc,int pos)
{
if(!spc)
spc=++tnt;
if(l==r)
{
tr[spc].val.vl++;
tr[spc].val.ps=pos;
return ;
}
int mid=(l+r)>>;
if(pos<=mid)
update(l,mid,tr[spc].ls,pos);
else
update(mid+,r,tr[spc].rs,pos);
pushup(spc);
return ;
}
void merge(int &spc1,int spc2)
{
if(!spc1||!spc2)
{
spc1|=spc2;
return ;
}
if(!tr[spc1].ls&&!tr[spc1].rs)
{
tr[spc1].val.vl+=tr[spc2].val.vl;
return ;
}
merge(tr[spc1].ls,tr[spc2].ls);
merge(tr[spc1].rs,tr[spc2].rs);
pushup(spc1);
return ;
}
int_2 query(int l,int r,int ll,int rr,int spc)
{
if(!spc||l>rr||ll>r)
return imt;
if(ll<=l&&r<=rr)
return tr[spc].val;
int mid=(l+r)>>;
return max(query(l,mid,ll,rr,tr[spc].ls),query(mid+,r,ll,rr,tr[spc].rs));
}
void Insert(int c)
{
int nwp,nwq,lsp,lsq;
nwp=++siz;
s[nwp].len=s[fin].len+;
for(lsp=fin;lsp&&!s[lsp].tranc[c];lsp=s[lsp].pre)
s[lsp].tranc[c]=nwp;
if(!lsp)
s[nwp].pre=;
else{
lsq=s[lsp].tranc[c];
if(s[lsq].len==s[lsp].len+)
s[nwp].pre=lsq;
else{
nwq=++siz;
s[nwq]=s[lsq];
s[nwq].len=s[lsp].len+;
s[nwp].pre=s[lsq].pre=nwq;
while(s[lsp].tranc[c]==lsq)
{
s[lsp].tranc[c]=nwq;
lsp=s[lsp].pre;
}
}
}
fin=nwp;
return ;
}
void Dfs(int x)
{
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
Dfs(to);
merge(p[x].rt,p[to].rt);
}
for(int i=;i<p[x].posquery.size();i++)
{
int h=p[x].posquery[i];
q[h].ans=query(,m,q[h].l,q[h].r,p[x].rt);
}
return ;
}
int main()
{
scanf("%s",str+);
n=strlen(str+);
scanf("%d",&m);
siz=;
for(int i=;i<=m;i++)
{
fin=;
scanf("%s",tmp+);
int tml=strlen(tmp+);
for(int j=;j<=tml;j++)
{
Insert(tmp[j]-'a');
update(,m,p[fin].rt,i);
}
}
for(int i=;i<=siz;i++)
ade(s[i].pre,i);
for(int i=;i<=siz;i++)
{
p[i].fa[]=s[i].pre;
}
for(int j=;j<=;j++){
for(int i=;i<=siz;i++)
{
p[i].fa[j]=p[p[i].fa[j-]].fa[j-]; }
}
scanf("%d",&Q);
for(int i=;i<=Q;i++)
{
q[i].Insert();
lpnt[q[i].pr].push_back(i);
}
int root=;
int lth=;
for(int i=;i<=n;i++)
{
int c=str[i]-'a';
while(root&&!s[root].tranc[c])
{
root=s[root].pre;
lth=s[root].len;
}
if(!root)
{
root=;
lth=;
continue;
}
root=s[root].tranc[c];
lth++;
for(int j=;j<lpnt[i].size();j++)
{
int h=lpnt[i][j];
int o=root;
if(lth<q[h].lt)
continue;
for(int k=;k>=;k--)
{
int nxt=p[o].fa[k];
if(s[nxt].len>=q[h].lt)
o=nxt;
}
p[o].posquery.push_back(h);
q[h].pos=o;
}
}
Dfs();
for(int i=;i<=Q;i++)
{
if(q[i].ans.vl==)
q[i].ans.ps=q[i].l;
printf("%d %d\n",q[i].ans.ps,q[i].ans.vl);
}
return ;
}