分析
用到了两个小套路：
-
使用线段树合并维护广义后缀自动机的(right)集合。
-
查询(S[L,R])在(T)中的出现次数：给(T)建SAM，在上面跑(S)，跑到(R)的时候先判匹配长度是否(geq R-L+1)，如果是则跳parent使(maxlen(x) geq R-L+1)的前提下(maxlen(x))最小（这个过程有时需要倍增优化），这个点的(|right(x)|)就是所求。
然后这道题就没了（大概）。
代码
#include <bits/stdc++.h>
#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;
using std::cin;
using std::cout;
using std::endl;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=500005;
int n,m,q,las,tot;
int ecnt,head[MAXN<<1];
int sgt,root[MAXN<<1],lc[MAXN*40],rc[MAXN*40],maxp[MAXN*40],maxn[MAXN*40];
int loc,ql,qr,retp,retn;
int mpos[MAXN],mmatch[MAXN];
int anc[MAXN<<1][21];
char s[MAXN],str[MAXN];
struct sam{
int fa,to[26];
int len;
}a[MAXN<<1];
struct Edge{
int to,nxt;
}e[MAXN<<1];
inline void add_edge(int bg,int ed){
++ecnt;
e[ecnt].to=ed;
e[ecnt].nxt=head[bg];
head[bg]=ecnt;
}
#define mid ((l+r)>>1)
inline void pushup(int o){
if(maxn[lc[o]]>=maxn[rc[o]]){
maxp[o]=maxp[lc[o]];
maxn[o]=maxn[lc[o]];
}
else{
maxp[o]=maxp[rc[o]];
maxn[o]=maxn[rc[o]];
}
}
int upd(int pre,int l,int r){
int o=pre;
if(!o) o=++sgt;
if(l==r){
maxp[o]=l;
++maxn[o];
return o;
}
if(loc<=mid) lc[o]=upd(lc[pre],l,mid);
else rc[o]=upd(rc[pre],mid+1,r);
pushup(o);
return o;
}
void query(int o,int l,int r){
if(ql<=l&&r<=qr){
if(retn<maxn[o]){
retp=maxp[o];
retn=maxn[o];
}
return;
}
if(mid>=ql) query(lc[o],l,mid);
if(mid<qr) query(rc[o],mid+1,r);
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x+y;
int o=++sgt;
if(l==r){
maxp[o]=l;
maxn[o]=maxn[x]+maxn[y];
return o;
}
lc[o]=merge(lc[x],lc[y],l,mid);
rc[o]=merge(rc[x],rc[y],mid+1,r);
pushup(o);
return o;
}
void write(int o,int l,int r){
if(l==r){
cout<<maxn[o]<<" ";
return;
}
write(lc[o],l,mid);
write(rc[o],mid+1,r);
}
#undef mid
void extend(int c,int idx){
int p=las,np=++tot;las=np;
a[np].len=a[p].len+1;
loc=idx;root[np]=upd(root[np],1,m);
while(p&&!a[p].to[c]){
a[p].to[c]=np;
p=a[p].fa;
}
if(!p){
a[np].fa=1;
return;
}
int q=a[p].to[c];
if(a[p].len+1==a[q].len){
a[np].fa=q;
return;
}
int nq=++tot;
a[nq]=a[q];
a[nq].len=a[p].len+1;
a[np].fa=a[q].fa=nq;
while(p&&a[p].to[c]==q){
a[p].to[c]=nq;
p=a[p].fa;
}
}
void dfs(int x){
trav(i,x){
int ver=e[i].to;
dfs(ver);
root[x]=merge(root[x],root[ver],1,m);
}
}
void match(){
int x=1,now=0;
rin(i,1,n){
while(x&&!a[x].to[s[i]]) x=a[x].fa,now=a[x].len;
if(!x){x=1,now=0;continue;}
x=a[x].to[s[i]],++now;
mpos[i]=x,mmatch[i]=now;
}
}
void buildanc(){
rin(i,1,tot) anc[i][0]=a[i].fa;
rin(i,1,20) rin(j,1,tot) anc[j][i]=anc[anc[j][i-1]][i-1];
}
inline int getanc(int x,int lim){
irin(i,20,0){
if(!anc[x][i]||a[anc[x][i]].len<lim) continue;
x=anc[x][i];
}
return x;
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
rin(i,1,n) s[i]-='a';
m=read();
tot=1;
rin(i,1,m){
scanf("%s",str+1);
int len=strlen(str+1);las=1;
rin(j,1,len) extend(str[j]-'a',i);
}
rin(i,2,tot) add_edge(a[i].fa,i);
dfs(1);buildanc();match();
q=read();
while(q--){
ql=read(),qr=read();int l=read(),r=read();
if(mmatch[r]<r-l+1){
printf("%d %d
",ql,0);
continue;
}
int x=mpos[r],y=getanc(x,r-l+1);
retp=retn=0;query(root[y],1,m);
if(retp==0) printf("%d %d
",ql,0);
else printf("%d %d
",retp,retn);
}
return 0;
}