题目传送门
分析：
把后面的串建一个广义SAM，每个点开一个线段树，下标是该点所在的串的编号，记录这个编号的T串里这个endpos集合子串的出现次数
Parent树上线段树合并
然后对S串每一个前缀的终点，找到其在SAM上对应的点和匹配长度
然后每次询问树上培增找到子串所在的endpos集合的点，查询这个点上的线段树即可
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#define maxn 1000005
#define INF 0x3f3f3f3f
using namespace std;
inline int getint()
{
int num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
int n,L;
char S[maxn],T[maxn];
int fir[maxn],nxt[maxn],to[maxn],cnt;
struct node{
int fa,nxt[26],len;
}t[maxn];
int lst,tot;
int p[maxn],len[maxn];
int rt[maxn],cur;
pair<int,int>a[maxn<<5];
int ch[maxn<<5][2];
int f[maxn][20];
inline pair<int,int> max(pair<int,int>x,pair<int,int>y)
{return (x.first==y.first?x.second>y.second:x.first<y.first)?y:x;}
inline void insert(int &now,int l,int r,int p)
{
if(!now)now=++cur;
if(l==r){a[now].first++,a[now].second=p;return;}
int mid=(l+r)>>1;
if(p<=mid)insert(ch[now][0],l,mid,p);
else insert(ch[now][1],mid+1,r,p);
a[now]=max(a[ch[now][0]],a[ch[now][1]]);
}
inline int merge(int x,int y,int l,int r)
{
if(!x||!y)return x|y;
int now=++cur;
if(l==r){a[now]=make_pair(a[x].first+a[y].first,a[x].second);return now;}
int mid=(l+r)>>1;
ch[now][0]=merge(ch[x][0],ch[y][0],l,mid);
ch[now][1]=merge(ch[x][1],ch[y][1],mid+1,r);
a[now]=max(a[ch[now][0]],a[ch[now][1]]);
return now;
}
inline pair<int,int> query(int now,int l,int r,int ql,int qr)
{
if(!now||qr<l||r<ql)return make_pair(0,0);
if(ql<=l&&r<=qr)return a[now];
int mid=(l+r)>>1;
return max(query(ch[now][0],l,mid,ql,qr),query(ch[now][1],mid+1,r,ql,qr));
}
inline void newnode(int u,int v)
{to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}
inline void dfs(int u)
{for(int i=fir[u];i;i=nxt[i])dfs(to[i]),rt[u]=merge(rt[u],rt[to[i]],1,n);}
inline void extend(int c,int id)
{
int p=lst,np=lst=++tot;
t[np].len=t[p].len+1;insert(rt[np],1,n,id);
while(p&&!t[p].nxt[c])t[p].nxt[c]=np,p=t[p].fa;
if(!p)t[np].fa=1;
else
{
int q=t[p].nxt[c];
if(t[q].len==t[p].len+1)t[np].fa=q;
else
{
int nq=++tot;
memcpy(t[nq].nxt,t[q].nxt,sizeof t[q].nxt);
t[nq].fa=t[q].fa;
t[nq].len=t[p].len+1;
t[q].fa=t[np].fa=nq;
while(p&&t[p].nxt[c]==q)t[p].nxt[c]=nq,p=t[p].fa;
}
}
}
int main()
{
scanf("%s",S+1);
n=getint();tot=1;
for(int i=1;i<=n;i++)
{
lst=1;scanf("%s",T+1);int tmp=strlen(T+1);
for(int j=1;j<=tmp;j++)extend(T[j]-'a',i);
}
for(int i=2;i<=tot;i++)newnode(t[i].fa,i),f[i][0]=t[i].fa;
for(int j=1;j<20;j++)for(int i=1;i<=tot;i++)f[i][j]=f[f[i][j-1]][j-1];
dfs(1);
L=strlen(S+1);int now=1,l=0;
for(int i=1;i<=L;i++)
{
if(t[now].nxt[S[i]-'a'])now=t[now].nxt[S[i]-'a'],l++;
else
{
while(now&&!t[now].nxt[S[i]-'a'])now=t[now].fa;
if(!now)now=1,l=0;
else l=t[now].len+1,now=t[now].nxt[S[i]-'a'];
}
p[i]=now,len[i]=l;
}
int Q=getint();
while(Q--)
{
int ql=getint(),qr=getint(),l=getint(),r=getint();
l=r-l+1;
if(l>len[r]){printf("%d 0
",ql);continue;}
r=p[r];
for(int i=19;~i;i--)if(f[r][i]&&t[f[r][i]].len>=l)r=f[r][i];
pair<int,int>tmp=query(rt[r],1,n,ql,qr);
if(!tmp.first)printf("%d 0
",ql);
else printf("%d %d
",tmp.second,tmp.first);
}
}
