一道大题.

Description

给出一个主串 $S$，$n$ 个匹配串编号从 $1$ 到 $n$。

$m$ 组询问，每次询问主串的一个子串 $S[pl,pr]$ 在编号为 $[l,r]$ 的匹配串的哪一个中出现次数最多。

Solution

建广义SAM. 对于每个匹配串, 我们希望在他每个子串所在节点都能有$1$的贡献, 我们可以在插入时关键节点上更新线段树, 然后做线段树合并. 线段树的值域是$[1,n]$.

对fail树倍增, 可以快速锁定一个主串的子串所在节点. 此时查询, 得到fail树上该节点子树的线段树情况, 也就是所有包含它的串都被存进了线段树, 查询区间最大值就得到了答案. 找位置就大概找一下就行.

就是代码比较长.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <bits/stdc++.h>

using namespace std;

const int maxn = 11e+5 + 5;

int m, pos[maxn];
int ls[maxn * 30], rs[maxn * 30], v[maxn * 30], id[maxn], cnt, n;
char str[maxn], t[maxn];

void update(int &cur, int l, int r, int p) {
  if (!cur) cur = ++cnt;
  if (l == r) {
    v[cur]++;
    // printf("%d\n", v[cur]);
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid) update(ls[cur], l, mid, p);
  else update(rs[cur], mid + 1, r, p);
  v[cur] = max(v[ls[cur]], v[rs[cur]]);
}
void merge(int &r1, int r2, int l, int r) {
  if (!r2) return;
  if (!r1) {
    r1 = r2; return;
  }
  int newrt = ++cnt; ls[newrt] = ls[r1]; rs[newrt] = rs[r1]; //v[newrt] = v[r1];
  if (l == r) {
    v[newrt] = v[r1] + v[r2];
    r1 = newrt;
    return;
  }
  int mid = (l + r) >> 1;
  merge(ls[newrt], ls[r2], l, mid);
  merge(rs[newrt], rs[r2], mid + 1, r);
  v[newrt] = max(v[ls[newrt]], v[rs[newrt]]);
  // printf("%d\n", v[newrt]);
  r1 = newrt;
}
int query(int cur, int l, int r, int L, int R) {
  if (L == l && r == R) return v[cur];
  int mid = (l + r) >> 1;
  if (R <= mid) return query(ls[cur], l, mid, L, R);
  else if (L > mid) return query(rs[cur], mid + 1, r, L, R);
  else return max(query(ls[cur], l, mid, L, mid), query(rs[cur], mid + 1, r, mid + 1, R));
}
int divide(int cur, int l, int r, int val) {
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (v[ls[cur]] == val) return divide(ls[cur], l, mid, val);
  else return divide(rs[cur], mid + 1, r, val);
}
int queryp(int cur, int l, int r, int L, int R, int val) {
  if (L == l && r == R) {
    if (v[cur] == val) return divide(cur, l, r, val);
    else return -1;
  }
  int mid = (l + r) >> 1;
  if (R <= mid) return queryp(ls[cur], l, mid, L, R, val);
  else if (L > mid) return queryp(rs[cur], mid + 1, r, L, R, val);
  else {
    int ret = queryp(ls[cur], l, mid, L, mid, val);
    if (ret != -1) return ret;
    else return queryp(rs[cur], mid + 1, r, mid + 1, R, val);
  }
}
struct SuffixAutomation {
  int tr[maxn][26], f[maxn][21], mx[maxn];
  int bkt[maxn], que[maxn], lst, tot;
  SuffixAutomation() {
    lst = tot = 1;
  }
  void insert(int ch, int idx) {
    int p, np, q, nq;
    if (tr[lst][ch]) {
      p = lst; q = tr[lst][ch];
      if (mx[q] == mx[p] + 1) {
        lst = q;
        if (idx) update(id[q], 1, m, idx);
      } else {
        nq = ++tot;
        mx[nq] = mx[p] + 1;
        lst = nq;
        if (idx) update(id[nq], 1, m, idx);
        memcpy(tr[nq], tr[q], sizeof tr[q]);
        f[nq][0] = f[q][0]; f[q][0] = nq;
        for (; p && tr[p][ch] == q; p = f[p][0]) 
          tr[p][ch] = nq;
      }
    } else {
      p = lst; np = ++tot; mx[np] = mx[p] + 1;
      lst = tot;
      if (idx) update(id[np], 1, m, idx);
      for (; p && !tr[p][ch]; p = f[p][0]) tr[p][ch] = np;
      if (!p) f[np][0] = 1;
      else {
        q = tr[p][ch];
        if (mx[q] == mx[p] + 1) f[np][0] = q;
        else {
          nq = ++tot; mx[nq] = mx[p] + 1;
          memcpy(tr[nq], tr[q], sizeof tr[q]);
          f[nq][0] = f[q][0]; f[np][0] = f[q][0] = nq;
          for (; p && tr[p][ch] == q; p = f[p][0]) tr[p][ch] = nq;
        }
      } 
      //lst = np;
    }
  }
  void RadixSort() {
    for (int i = 1; i <= tot; ++i) bkt[mx[i]]++;
    for (int i = 1; i <= tot; ++i) bkt[i] += bkt[i - 1];
    for (int i = tot; i; --i)
      que[bkt[mx[i]]--] = i;
  }
}SAM;

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}

int main() {
  scanf("%s", str + 1);
  int l = strlen(str + 1);
  for (int i = 1; i <= l; ++i) {
    SAM.insert(str[i] - 'a', 0);
    pos[i] = SAM.lst;
    //printf("%d\n", pos[i]);
  }

  m = rd();
  for (int i = 1; i <= m; ++i) {
    scanf("%s", t + 1); l = strlen(t + 1);
    SAM.lst = 1;
    for (int j = 1; j <= l; ++j)
      SAM.insert(t[j] - 'a', i);
  } 

  for (int i = 1; i <= 20; ++i)
    for (int j = 1; j <= SAM.tot; ++j)
      SAM.f[j][i] = SAM.f[SAM.f[j][i - 1]][i - 1];
  SAM.RadixSort();
  for (int i = SAM.tot; i; --i) {
    int x = SAM.que[i];
    // printf("%d\n", x);
    if (SAM.f[x][0])
      merge(id[SAM.f[x][0]], id[x], 1, m);
  }

  int q = rd(), tl, tr, L, R, mxv, mxp;
  while (q--) {
    tl = rd(); tr = rd(); L = rd(); R = rd();
    int u = pos[R];
    for (int j = 20; ~j; --j)
      if (SAM.mx[SAM.f[u][j]] >= R - L + 1) u = SAM.f[u][j];
    mxv = query(id[u], 1, m, tl, tr);
    mxp = queryp(id[u], 1, m, tl, tr, mxv);
    printf("%d %d\n", mxp, mxv);
  }
  return 0;
}