首先建立广义SAM，求匹配位置直接 f a i l fail fail 树上倍增即可。
至于匹配次数，直接对于所有 n n n个串来一个线段树合并即可。
然后就没了。。。非常套路，没什么细节。
代码：
#include<bits/stdc++.h> #define ll long long #define re register #define cs const namespace IO{ inline char gc(){ static cs int Rlen=1<<22|1; static char buf[Rlen],*p1,*p2; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; } inline int get_s(char *s){ int len=0;char c; while(isspace(c=gc())); while(s[len++]=c,!isspace(c=gc())&&c!=EOF); return s[len]='\0',len; } template<typename T> inline T get(){ char c;T num; while(!isdigit(c=gc()));num=c^48; while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48); return num; } inline int gi(){return get<int>();} } using namespace IO; using std::cerr; using std::cout; using pii=std::pair<int,int>; #define fi first #define se second cs int N=5e5+7,M=5e4+7; int n,m; char s[N]; int sl,ps[N],ml[N]; char t[N];int tl; namespace SGT{ cs int N=::M*160; int lc[N],rc[N],tot;pii mx[N]; inline int _copy(int u){++tot;lc[tot]=lc[u],rc[tot]=rc[u],mx[tot]=mx[u];return tot;} inline void ins(int &u,int l,int r,int p){ if(!u)u=++tot;if(l==r){mx[u].fi++,mx[u].se=-l;return ;} int mid=l+r>>1; (p<=mid)?ins(lc[u],l,mid,p):ins(rc[u],mid+1,r,p); mx[u]=std::max(mx[lc[u]],mx[rc[u]]); } inline void merge(int &u,int v,int l,int r){ if(!u||!v){u|=v;return ;} u=_copy(u);if(l==r){mx[u].fi+=mx[v].fi;return ;} int mid=l+r>>1; merge(lc[u],lc[v],l,mid); merge(rc[u],rc[v],mid+1,r); mx[u]=std::max(mx[lc[u]],mx[rc[u]]); } inline pii query(int u,int l,int r,int ql,int qr){ if(!u)return pii(0,0); if(ql<=l&&r<=qr)return mx[u]; int mid=l+r>>1; if(qr<=mid)return query(lc[u],l,mid,ql,qr); if(mid<ql)return query(rc[u],mid+1,r,ql,qr); return std::max(query(lc[u],l,mid,ql,qr),query(rc[u],mid+1,r,ql,qr)); } } int rt[M<<1|1]; namespace SAM{ cs int N=::M<<1|1; int fa[N],son[N][26],len[N],f[18][N],now=1,last; inline int work(int p,int c){ int nq=++now,q=son[p][c]; memcpy(son[nq],son[q],sizeof son[q]); len[nq]=len[p]+1,fa[nq]=fa[q],fa[q]=nq; for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq; return nq; } inline void push_back(int c,int id){ int p=last; if(son[p][c]){ if(len[son[p][c]]==len[p]+1)last=son[p][c]; else last=work(p,c); } else { int cur=last=++now;len[cur]=len[p]+1; for(;p&&!son[p][c];p=fa[p])son[p][c]=cur; if(!p)fa[cur]=1; else if(len[son[p][c]]==len[p]+1)fa[cur]=son[p][c]; else fa[cur]=work(p,c); } SGT::ins(rt[last],1,n,id); } inline void trans(int &u,int &nl,int c){ while(u&&!son[u][c])u=fa[u],nl=len[u]; if(!u)u=1,nl=0; else ++nl,u=son[u][c]; } inline int jump(int u,int L){ for(int re i=17;~i;--i)if(f[i][u]&&len[f[i][u]]>=L)u=f[i][u]; return u; } int bin[N],nd[N]; inline void radix_sort(){ for(int re i=1;i<=now;++i)++bin[len[i]]; for(int re i=1;i<=now;++i)bin[i]+=bin[i-1]; for(int re i=now;i;--i)nd[bin[len[i]]--]=i; for(int re i=now;i;--i)if(fa[nd[i]])SGT::merge(rt[fa[nd[i]]],rt[nd[i]],1,n); for(int re i=1;i<=now;++i){ int u=nd[i];f[0][u]=fa[u]; for(int re j=0;f[j][u];++j)f[j+1][u]=f[j][f[j][u]]; } } } signed main(){ #ifdef zxyoi freopen("forensic.in","r",stdin); #endif sl=get_s(s+1);n=gi(); for(int re i=1;i<=n;++i){ tl=get_s(t+1);SAM::last=1; for(int re j=1;j<=tl;++j)SAM::push_back(t[j]-'a',i); } SAM::radix_sort();int p=1,nowl=0; for(int re i=1;i<=sl;++i){ SAM::trans(p,nowl,s[i]-'a'); ps[i]=p,ml[i]=nowl; } m=gi(); while(m--){ int l=gi(),r=gi(),pl=gi(),pr=gi(); if(pr-pl+1>ml[pr])cout<<l<<" 0\n"; else { int u=SAM::jump(ps[pr],pr-pl+1); pii t=SGT::query(rt[u],1,n,l,r); if(t.fi==0)t.se=-l; cout<<-t.se<<" "<<t.fi<<"\n"; } } return 0; }