将所有串（包括S）放一块建SAM。对于询问，倍增定位出该子串所在节点，然后要查询的就是该子串在区间内的哪个字符串出现最多。可以线段树合并求出该节点在每个字符串中的出现次数。

#include
     
      using namespace std;#define ll long long#define N 1100010char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){	int x=0,f=1;char c=getchar();	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();	return x*f;}typedef pair
      
        pii;char s[N];int n,m,Q,cnt=1,last,id[N],fail[N],len[N],root[N],f[N][22],q[N],tmp[N],tot=0;map
       
         son[N];struct data{int l,r;pii t;}tree[N*22];pii operator +(const pii&a,const pii&b){	return make_pair(a.first+b.first,a.second);}pii Max(pii a,pii b){return a.first>b.first||a.first==b.first&&a.second
        
         >1;	if (x<=mid) ins(tree[k].l,l,mid,x);	else ins(tree[k].r,mid+1,r,x);	tree[k].t=Max(tree[tree[k].l].t,tree[tree[k].r].t);}int merge(int x,int y,int l,int r){	if (!x||!y) return x|y;	int k=++tot;	if (l==r) tree[k].t=tree[x].t+tree[y].t;	else	{		int mid=l+r>>1;		tree[k].l=merge(tree[x].l,tree[y].l,l,mid);		tree[k].r=merge(tree[x].r,tree[y].r,mid+1,r);		tree[k].t=Max(tree[tree[k].l].t,tree[tree[k].r].t);	}	return k;}pii query(int k,int l,int r,int x,int y){	if (!k||l==x&&r==y) return tree[k].t;	int mid=l+r>>1;	if (y<=mid) return query(tree[k].l,l,mid,x,y);	else if (x>mid) return query(tree[k].r,mid+1,r,x,y);	else return Max(query(tree[k].l,l,mid,x,mid),query(tree[k].r,mid+1,r,mid+1,y));}int extend(int p,int c,int i,int j){	int u;	if (son[p][c])	{		int q=son[p][c];		if (len[p]+1==len[q]) u=q;		else		{			int y=++cnt;			len[y]=len[p]+1;			son[y]=son[q];			fail[y]=fail[q],fail[q]=y;			while (son[p][c]==q) son[p][c]=y,p=fail[p];			u=y;		}	}	else	{		int x=++cnt;len[x]=len[p]+1;		while (!son[p][c]&&p) son[p][c]=x,p=fail[p];		if (!p) fail[x]=1;		else		{			int q=son[p][c];			if (len[p]+1==len[q]) fail[x]=q;			else			{				int y=++cnt;				len[y]=len[p]+1;				son[y]=son[q];				fail[y]=fail[q],fail[q]=fail[x]=y;				while (son[p][c]==q) son[p][c]=y,p=fail[p];			}		}		u=x;	}	if (i==0) id[j]=u;	else ins(root[u],1,m,i);	return u;}int getpos(int k,int x){	for (int j=21;~j;j--) if (len[f[k][j]]>=x) k=f[k][j];	return k;}int main(){#ifndef ONLINE_JUDGE	freopen("a.in","r",stdin);	freopen("a.out","w",stdout);#endif	scanf("%s",s+1);n=strlen(s+1);	last=1;for (int i=1;i<=n;i++) last=extend(last,s[i]-'a',0,i);	m=read();	for (int i=1;i<=m;i++)	{		scanf("%s",s+1);int _=strlen(s+1);		last=1;for (int j=1;j<=_;j++) last=extend(last,s[j]-'a',i,j);	}	for (int i=1;i<=cnt;i++) f[i][0]=fail[i];f[1][0]=1;	for (int j=1;j<=21;j++)		for (int i=1;i<=cnt;i++)		f[i][j]=f[f[i][j-1]][j-1];	for (int i=1;i<=cnt;i++) tmp[len[i]]++;	for (int i=1;i<=cnt;i++) tmp[i]+=tmp[i-1];	for (int i=1;i<=cnt;i++) q[tmp[len[i]]--]=i;	for (int i=cnt;i>=1;i--)	{		int x=q[i];		root[fail[x]]=merge(root[fail[x]],root[x],1,m);	}	Q=read();	while (Q--)	{		int l=read(),r=read(),pl=read(),pr=read();		int x=getpos(id[pr],pr-pl+1);		pii t=query(root[x],1,m,l,r);		printf("%d %d\n",max(l,t.second),t.first);	}	return 0;}