之前发的帖子已经删掉了qaq 代码有点问题)蒟蒻调了一晚上了一直挂在test2 答案是 3 0
蒟蒻代码输出 13 1
思路就是建立广义 SAM 之后线段树合并在 parent 树上维护每个点在每个串中的出现次数,然后在 parent 树上倍增
#include<bits/stdc++.h>
using namespace std;
const int SN=2e6+10;
const int N=4e6+10;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
const int inf=(1<<30);
typedef pair<int,int> pr;
#define fi first
#define se second
#define mp make_pair
inline pr Max(pr x,pr y){
if(x.se==y.se)return x.fi<y.fi?x:y;
return x.se>y.se?x:y;
}
int qy,m,pos[SN];
namespace SGT{
int ls[N],rs[N],node;
pr mxpos[N];
inline void pushup(const int &x){mxpos[x]=Max(mxpos[ls[x]],mxpos[rs[x]]);}
void change(int &x,const int &L,const int &R,const int &pos){
if(!x)x=++node;
if(L==R){
mxpos[x].fi=L;
mxpos[x].se++;
return;
}
int mid=(L+R)>>1;
if(pos<=mid)change(ls[x],L,mid,pos);
else change(rs[x],mid+1,R,pos);
pushup(x);
}
int merge(const int &x,const int &y,const int &L,const int &R){
if(!x||!y)return x|y;
int p=++node;
int mid=(L+R)>>1;
if(L==R){
mxpos[p].fi=L;
mxpos[p].se=mxpos[x].se+mxpos[y].se;
return p;
}
ls[p]=merge(ls[x],ls[y],L,mid);
rs[p]=merge(rs[x],rs[y],mid+1,R);
pushup(p);return p;
}
pr query(const int &x,const int &L,const int &R,const int &l,const int &r){
if(L>=l&&R<=r){return mxpos[x];}
int mid=(L+R)>>1;
if(l<=mid&&!(mid<r))return query(ls[x],L,mid,l,r);
if(mid<r&&!(l<=mid))return query(rs[x],mid+1,R,l,r);
return Max(query(ls[x],L,mid,l,r),query(rs[x],mid+1,R,l,r));
}
}
using namespace SGT;
namespace SAM{
int len[SN],pa[SN],ch[SN][26],rt[SN],tot=1,last=1,col[SN],f[SN][23];
vector<int>G[SN];
void insert(const int &c,const int &cl){
int p=last;int np=++tot;last=tot;
len[np]=len[p]+1;
for(;p&&!ch[p][c];p=pa[p])ch[p][c]=np;
if(!p)pa[np]=1;
else{
int q=ch[p][c];
if(len[q]==len[p]+1)pa[np]=q;
else{
int nq=++tot;
len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof ch[q]);
pa[nq]=pa[q];pa[q]=pa[np]=nq;
for(;p&&ch[p][c]==q;p=pa[p])ch[p][c]=nq;
}
}
}
void dfs(int x){
for(auto v:G[x]){
f[v][0]=x;
for(int i=1;i<23;++i)f[v][i]=f[f[v][i-1]][i-1];
dfs(v);
rt[x]=merge(rt[x],rt[v],1,m);
}
}
void Build(){
for(int i=2;i<=tot;++i)G[pa[i]].push_back(i);
dfs(1);
}
}
using namespace SAM;
char s[SN];
string t[SN];
void solve(int sl,int sr,int tl,int tr){
int spos=pos[sr];
if(!spos){
printf("%d 0\n",tl);
return;
}
int lens=sr-sl+1;
int now=spos;
for(int i=22;~i;--i){if(now&&len[f[now][i]]>=lens)now=f[now][i];}
if(!now||now==1||len[now]<lens){
printf("%d 0\n",tl);
return;
}
pr Ans=query(rt[now],1,m,tl,tr);
if(!Ans.se)Ans.fi=tl;
printf("%d %d\n",Ans.fi,Ans.se);
}
int main(){
scanf("%s",s+1);
scanf("%d",&m);
for(int i=1;i<=m;++i){
last=1;
cin>>t[i];
int tlen=t[i].size();
for(int j=1;j<=tlen;++j){
int v=t[i][j-1]-'a';
insert(v,i);
}
}
for(int i=1;i<=m;++i){
int tlen=t[i].size();
int now=1;
for(int j=0;j<tlen;++j){
int v=t[i][j]-'a';
now=ch[now][v];
change(rt[now],1,m,i);
}
}
Build();
int now=1;
for(int i=1;i<=(int)strlen(s+1);++i){
int v=s[i]-'a';
while(now&&!ch[now][v])now=pa[now];
if(!now)now=1;
else now=ch[now][v],pos[i]=now;
}
scanf("%d",&qy);
while(qy--){
int sl,sr,tl,tr;
scanf("%d%d%d%d",&tl,&tr,&sl,&sr);
solve(sl,sr,tl,tr);
}
return 0;
}