题意：
给你一个串S以及一个字符串数组T[1..m]，q次询问，每次问S的子串S[pl..pr]在T[l..r]中的哪个串里的出现次数最多，并输出出现次数。
如有多解输出最靠前的那一个。
解：
什么奇葩排版......
对T建广义SAM，线段树合并维护每个节点有哪些串。写法稍微注意一下。
记录下s在t上匹配的时候每个前缀走到哪个位置。然后树上倍增找到符合条件的节点，线段树上查询。
如果查到0或者根本没那么长的匹配长度，输出"L 0"
1 #include2 #include 3 #include 4 #include 5 #include 6 7 const int N = 500010, M = 20000010; 8 9 struct Edge { 10 int nex, v; 11 }edge[N * 2]; int tp; 12 13 char str[N]; 14 int tr[N * 2][26], len[N * 2], fail[N * 2], tot = 1, n, m, L, R, e[N * 2], cnt; 15 std::string ss[N]; 16 int large[M], ans[M], rt[N * 2], ls[M], rs[M], pos[N], lenth[N], fa[N * 2][20], pw[N * 2]; 17 18 inline void add(int x, int y) { 19 tp++; 20 edge[tp].v = y; 21 edge[tp].nex = e[x]; 22 e[x] = tp; 23 return; 24 } 25 26 inline void Max(int &a, int b) { 27 if(!b) return; 28 if(large[b] > large[a] || (large[b] == large[a] && ans[a] > ans[b])) { 29 a = b; 30 } 31 return; 32 } 33 34 inline void pushup(int o) { 35 large[o] = std::max(large[ls[o]], large[rs[o]]); 36 if(large[ls[o]] > large[rs[o]]) { 37 ans[o] = ans[ls[o]]; 38 } 39 else if(large[rs[o]] > large[ls[o]]) { 40 ans[o] = ans[rs[o]]; 41 } 42 else ans[o] = std::min(ans[ls[o]], ans[rs[o]]); 43 return; 44 } 45 46 inline void insert(int p, int l, int r, int &o) { 47 if(!o) o = ++cnt; 48 if(l == r) { 49 ans[o] = r; 50 large[o]++; 51 return; 52 } 53 int mid = (l + r) >> 1; 54 if(p <= mid) insert(p, l, mid, ls[o]); 55 else insert(p, mid + 1, r, rs[o]); 56 pushup(o); 57 return; 58 } 59 60 inline int merge(int x, int y, int l, int r) { 61 if(!x || !y) return x | y; 62 if(l == r) { 63 int o = ++cnt; 64 large[o] = large[x] + large[y]; 65 ans[o] = r; 66 return o; 67 } 68 int o = ++cnt, mid = (l + r) >> 1; 69 ls[o] = merge(ls[x], ls[y], l, mid); 70 rs[o] = merge(rs[x], rs[y], mid + 1, r); 71 pushup(o); 72 return o; 73 } 74 75 void out(int l, int r, int x) { 76 if(!x) printf("!x"); 77 printf("(%d [%d %d] lar=%d ans=%d) ", x, l, r, large[x], ans[x]); 78 if(l == r) { 79 printf("%d ", r); 80 return; 81 } 82 int mid = (l + r) >> 1; 83 if(ls[x]) out(l, mid, ls[x]); 84 if(rs[x]) out(mid + 1, r, rs[x]); 85 return; 86 } 87 88 void DFS(int x) { 89 for(int i = e[x]; i; i = edge[i].nex) { 90 int y = edge[i].v; 91 DFS(y); 92 rt[x] = merge(rt[x], rt[y], 1, m); 93 } 94 return; 95 } 96 97 inline int ask(int l, int r, int o) { /// return a Node 98 if(!o) return 0; 99 if(L <= l && r <= R) return o;100 int mid = (l + r) >> 1, Ans = 0;101 if(L <= mid) Max(Ans, ask(l, mid, ls[o]));102 if(mid < R) Max(Ans, ask(mid + 1, r, rs[o]));103 return Ans;104 }105 106 inline int split(int p, int f) {107 int Q = tr[p][f], nQ = ++tot;108 len[nQ] = len[p] + 1;109 fail[nQ] = fail[Q];110 fail[Q] = nQ;111 memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));112 while(tr[p][f] == Q) {113 tr[p][f] = nQ;114 p = fail[p];115 }116 return nQ;117 }118 119 inline int insert(char c, int p, int id) {120 int f = c - 'a', np;121 if(tr[p][f]) {122 int Q = tr[p][f];123 if(len[Q] == len[p] + 1) {124 np = Q;125 }126 else np = split(p, f);127 insert(id, 1, m, rt[np]);128 return np;129 }130 np = ++tot;131 len[np] = len[p] + 1;132 while(p && !tr[p][f]) {133 tr[p][f] = np;134 p = fail[p];135 }136 if(!p) {137 fail[np] = 1;138 }139 else {140 int Q = tr[p][f];141 if(len[Q] == len[p] + 1) {142 fail[np] = Q;143 }144 else {145 fail[np] = split(p, f);146 }147 }148 insert(id, 1, m, rt[np]);149 return np;150 }151 152 inline int getpos(int l, int r) {153 int p = pos[r], Len = r - l + 1;154 if(lenth[r] < Len) return 0;155 int t = pw[tot];156 while(t >= 0) {157 if(len[fa[p][t]] >= Len) {158 p = fa[p][t];159 }160 t--;161 }162 return p;163 }164 165 int main() {166 scanf("%s", str + 1);167 n = strlen(str + 1);168 scanf("%d", &m);169 for(int i = 1; i <= m; i++) {170 std::cin >> ss[i];171 int k = ss[i].size(), p = 1;172 for(int j = 0; j < k; j++) {173 p = insert(ss[i][j], p, i);174 }175 }176 /// insert OVER177 for(int i = 2; i <= tot; i++) {178 add(fail[i], i);179 fa[i][0] = fail[i];180 }181 DFS(1);182 for(int i = 2; i <= tot; i++) pw[i] = pw[i >> 1] + 1;183 for(int j = 1; j <= pw[tot]; j++) {184 for(int i = 1; i <= tot; i++) {185 fa[i][j] = fa[fa[i][j - 1]][j - 1];186 }187 }188 int Len = 0, p = 1;189 for(int i = 1; i <= n; i++) {190 int ff = str[i] - 'a';191 while(p && !tr[p][ff]) {192 p = fail[p];193 Len = len[p];194 }195 if(!p) {196 p = 1;197 }198 else {199 p = tr[p][ff];200 Len++;201 }202 pos[i] = p;203 lenth[i] = Len;204 }205 /// prework OVER206 int q, l, r;207 scanf("%d", &q);208 for(int i = 1; i <= q; i++) {209 scanf("%d%d%d%d", &L, &R, &l, &r);210 p = getpos(l, r);211 if(!p) printf("%d 0\n", L);212 else {213 int Ans = ask(1, m, rt[p]);214 if(!Ans) printf("%d 0\n", L);215 else printf("%d %d\n", ans[Ans], large[Ans]);216 }217 }218 return 0;219 }
我调了一晚上差点气疯了，结果是因为tr数组第二维只开了2...这个数组脱离我的控制...