The country of Reberland is the archenemy of Berland. Recently the authorities of Berland arrested a Reberlandian spy who tried to bring the leaflets intended for agitational propaganda to Berland illegally . The most leaflets contain substrings of the Absolutely Inadmissible Swearword and maybe even the whole word.
Berland legal system uses the difficult algorithm in order to determine the guilt of the spy. The main part of this algorithm is the following procedure.
All the m leaflets that are brought by the spy are numbered from 1 to m. After that it's needed to get the answer to q queries of the following kind: "In which leaflet in the segment of numbers [l, r] the substring of the Absolutely Inadmissible Swearword [pl, pr] occurs more often?".
The expert wants you to automate that procedure because this time texts of leaflets are too long. Help him!
The first line contains the string s (1 ≤ |s| ≤ 5·105) — the Absolutely Inadmissible Swearword. The string s consists of only lowercase English letters.
The second line contains the only integer m (1 ≤ m ≤ 5·104) — the number of texts of leaflets for expertise.
Each of the next m lines contains the only string ti — the text of the i-th leaflet. The sum of lengths of all leaflet texts doesn't exceed 5·104. The text of the leaflets consists of only lowercase English letters.
The next line contains integer q (1 ≤ q ≤ 5·105) — the number of queries for expertise.
Finally, each of the last q lines contains four integers l, r, pl, pr (1 ≤ l ≤ r ≤ m, 1 ≤ pl ≤ pr ≤ |s|), where |s| is the length of the Absolutely Inadmissible Swearword.
Print q lines. The i-th of them should contain two integers — the number of the text with the most occurences and the number of occurences of the substring [pl, pr] of the string s. If there are several text numbers print the smallest one.
suffixtree
3
suffixtreesareawesome
cartesiantreeisworsethansegmenttree
nyeeheeheee
2
1 2 1 10
1 3 9 10
1 1
3 4
给出一个主串和m个模式串，有Q次询问，每次询问第L个到第R个模式串中，主串的[pl,pr]子串在哪个串中出现次数最多，输出最多的出现次数和其对应的模式串编号。
字符串 广义后缀自动机 线段树合并
先用模式串建广义后缀自动机，每个结点开一颗线段树，存它的right集里有哪些串。
然后按照套路对结点进行基数排序，合并right集合（即合并线段树）。
查询的时候，在自动机上找到包含目标串[pl,pr]的最浅的结点，在它对应的线段树上查询区间众数。
一个j打成i调了近一个小时，之后零碎的边界问题又调了近一个小时
代码蜜汁长
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int mxn=1100010; 8 int read(){ 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 // 15 int ans,anspos=0; 16 struct SGT{ 17 struct node{ 18 int l,r; 19 int val,mxpos; 20 }t[mxn<<3]; 21 int rot[mxn],sz=0; 22 #define lc t[rt].l 23 #define rc t[rt].r 24 void pushup(int rt){ 25 if(t[lc].val>=t[rc].val){ 26 t[rt].val=t[lc].val;t[rt].mxpos=t[lc].mxpos; 27 } 28 else{ t[rt].val=t[rc].val;t[rt].mxpos=t[rc].mxpos; } 29 return; 30 } 31 void update(int p,int v,int l,int r,int &rt){ 32 if(!rt)rt=++sz; 33 if(l==r){ 34 t[rt].val++; 35 t[rt].mxpos=p; 36 return; 37 } 38 int mid=(l+r)>>1; 39 if(p<=mid)update(p,v,l,mid,lc); 40 else update(p,v,mid+1,r,rc); 41 pushup(rt); 42 return; 43 } 44 int merge(int x,int y,int l,int r){ 45 if(!x || !y)return x+y; 46 int res=++sz; 47 if(l==r){ 48 t[res].val=t[x].val+t[y].val; 49 t[res].mxpos=l; 50 return res; 51 } 52 int mid=(l+r)>>1; 53 t[res].l=merge(t[x].l,t[y].l,l,mid); 54 t[res].r=merge(t[x].r,t[y].r,mid+1,r); 55 pushup(res); 56 return res; 57 } 58 void query(int L,int R,int l,int r,int rt){ 59 if(L<=l && r<=R){ 60 if(t[rt].val>ans){ 61 ans=t[rt].val; 62 anspos=t[rt].mxpos; 63 } 64 else if(t[rt].val==ans)anspos=min(anspos,t[rt].mxpos); 65 return; 66 } 67 int mid=(l+r)>>1; 68 if(L<=mid)query(L,R,l,mid,lc); 69 if(R>mid)query(L,R,mid+1,r,rc); 70 return; 71 } 72 }sgt; 73 // 74 int pos[mxn]; 75 int ls[mxn]; 76 int m; 77 struct SAM{ 78 int t[mxn][26],fa[mxn][22]; 79 int len[mxn]; 80 int S,last,cnt; 81 void init(){S=last=cnt=1;return;} 82 void add(int c,int id){ 83 if(t[last][c] && len[t[last][c]]==len[last]+1){ 84 last=t[last][c];return; 85 }// 86 int p=last,np=++cnt;last=np; 87 len[np]=len[p]+1; 88 for(;p && !t[p][c];p=fa[p][0])t[p][c]=np; 89 if(!p){ 90 fa[np][0]=S; 91 } 92 else{ 93 int q=t[p][c]; 94 if(len[q]==len[p]+1){ 95 fa[np][0]=q; 96 } 97 else{ 98 int nq=++cnt; 99 len[nq]=len[p]+1; 100 memcpy(t[nq],t[q],sizeof t[q]); 101 fa[nq][0]=fa[q][0]; 102 fa[q][0]=fa[np][0]=nq; 103 for(;p && t[p][c]==q;p=fa[p][0])t[p][c]=nq; 104 } 105 } 106 return; 107 } 108 int w[mxn],rk[mxn]; 109 void sst(){ 110 for(int i=1;i<=cnt;i++)w[len[i]]++; 111 for(int i=1;i<=cnt;i++)w[i]+=w[i-1]; 112 for(int i=1;i<=cnt;i++)rk[w[len[i]]--]=i; 113 for(int i=cnt;i;i--){ 114 if(rk[i]){ 115 int tp=rk[i]; 116 sgt.rot[fa[tp][0]]=sgt.merge(sgt.rot[fa[tp][0]],sgt.rot[tp],1,m); 117 } 118 } 119 for(int j=1;j<=21;j++) 120 for(int i=1;i<=cnt;i++) 121 fa[i][j]=fa[fa[i][j-1]][j-1]; 122 return; 123 } 124 int find(int x,int lim){ 125 for(int i=21;i>=0;i--){ 126 if(len[fa[x][i]]>=lim)x=fa[x][i]; 127 } 128 return x; 129 } 130 void solve(){ 131 int L=read(),R=read(),pl=read(),pr=read(); 132 if(ls[pr]<pr-pl+1){ 133 printf("%d %d ",L,0); 134 return; 135 } 136 int x=find(pos[pr],pr-pl+1); 137 ans=0;anspos=0; 138 sgt.query(L,R,1,m,sgt.rot[x]); 139 if(!ans)anspos=L; 140 printf("%d %d ",anspos,ans); 141 return; 142 } 143 }sa; 144 char s[mxn]; 145 char c[mxn]; 146 int main(){ 147 int i,j; 148 sa.init(); 149 scanf("%s",s+1); 150 int len; 151 m=read(); 152 for(i=1;i<=m;i++){ 153 scanf("%s",c+1); 154 len=strlen(c+1); 155 for(j=1;j<=len;j++){ 156 sa.add(c[j]-'a',i); 157 sgt.update(i,1,1,m,sgt.rot[sa.last]); 158 } 159 sa.last=sa.S; 160 } 161 len=strlen(s+1); 162 int now=sa.S,nl=0; 163 for(i=1;i<=len;i++){ 164 int c=s[i]-'a'; 165 while(now!=sa.S && !sa.t[now][c])now=sa.fa[now][0],nl=sa.len[now]; 166 if(sa.t[now][c]){ 167 now=sa.t[now][c];nl=nl+1; 168 pos[i]=now;ls[i]=nl; 169 } 170 } 171 sa.sst(); 172 int Q=read(); 173 while(Q--)sa.solve(); 174 return 0; 175 }