后缀XXX可持久化大坑

发表于 | 分类于

我谔谔，我今天才学的后缀数组（之前只会后缀自动机）。

然后就想开个后缀家族大坑？

后缀数组

介绍

虽然说可能在各位巨佬眼里这已经是烂大街的东西了……但我现在才会（逃

思想很简单吧，对于原串的所有后缀排个序（按字典序升序），形成了一个数组\(\mathrm{sa}\)，就叫做后缀数组，方便起见定义\(\mathrm{rk}[i]\)表示\(i\ldots n\)这一段后缀在\(\mathrm{sa}\)中的排名。

然后考虑怎么求这玩意吧……

倍增排序求SA

如果直接按照定义，快排加暴力比较弄的话，\(O(n^2\log n)\)的复杂度没什么用（其实有个比较贱的方法事你可以预处理哈希然后二分比较两个后缀就匪快了）。

我们考虑采取倍增的思想，依次比较各个后缀的长度为\(1,2,4,8,16,\ldots\)的前缀，这样的话总是可以比较出最后的结果。

更大的好处是，假如我们已经有了\(2^t\)下的答案，我们要对\(2^{t + 1}\)的情况排序。那么每个后缀我们可以直接视为一个二元组\((a, b)\)，其中\(a,b\)分别是\(2^t\)下的排名。

这样的话我们可以直接用这种思想套上快排，复杂度\(O(n\log^2 n)\)。但观察到二元组的两元的值域都不超过\(n\)，所以把快排改成桶排，这样复杂度就是\(O(n\log n)\)的了。

然后更多细节参考代码吧。

SA的应用：height数组

这样看的话SA好像没啥用处？

我们定义一个\(\mathrm{height}[i]\)表示排名为\(i\)的后缀和他的上一名的LCP。如果你学过后缀树的话，你会发现把后缀树的叶子按照对应后缀字典序排序一下，然后这个\(\mathrm{height}\)就是每个叶子和他左侧的叶子的LCA的深度。

直接按照定义求这玩意显然复杂度\(O(n^2)\)，难以接受。然后我们定义\(h(i) = \mathrm{height}[\mathrm{rk}[i]]\)，然后我们发现有： \[ h(i)\geq h(i - 1) - 1 \] 证明的话考虑\(h(i - 1)\geq 1\)的情况就行了。我们假设\(a = i - 1, b = \mathrm{sa}[\mathrm{rk}[a] - 1]\)，那么若\(h(i - 1)\geq 1\)，那么我们把两者截去开头一个字符还会得到两个新的后缀\(a',b'\)，注意到有\(a' = i, b' = b + 1\)，且\(\mathbf{LCP}(a',b') = h(i - 1) - 1\)，考虑到字典序意义上\(a > b\)，那么显然字典序意义下也有\(i > b + 1\)，那么说明\(\mathrm{rk}[i] - 1\leq b + 1\)，因此\(\mathrm{sa}[\mathrm{rk}[i] - 1]\)在排序后的后缀树中一定不会比\(b + 1\)离\(i\)更远，换言之\(\mathrm{sa}[\mathrm{rk}[i] - 1]\)和\(i\)在树中的LCA深度（也就是串中的LCP大小）不会小于\(h(i - 1) - 1\)。

根据这个东西，就可以很轻松的\(O(n)\)求出\(\mathrm{height}\)数组了。

题目

POJ 2774 Long Long Message

Description

给两个串，求两者的最长公共子串。

两个串的长度都不超过100000。

Solution

考虑把两个串强行接在一起（顺便中间加上一个特殊字符作为分隔符以防越界），那么两者的公共子串一定是某两个在分隔符两端的后缀的公共前缀，而我们要取出最长的情况。

那么我们按照\(\mathrm{sa}\)的顺序扫描所有后缀，如果出现相邻两个后缀在分隔符两侧，那就取他们的\(\mathrm{height}\)值更新答案即可。

Code

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <functional>
#include <utility>
int idx(char c) {
  if(c == '$') {
    return 27;
  } else {
    return c - 'a' + 1;
  }
}

const int maxn = 200005;
char S[maxn]; int sz;
int sa[maxn], rk[maxn], height[maxn];
void process() {
  static int fir[maxn], sec[maxn];
  static int buf[maxn], tmp[maxn];
  for(int i = 1; i <= sz; i ++) buf[idx(S[i])] ++;
  for(int i = 1; i <= 27; i ++) buf[i] += buf[i - 1];
  for(int i = 1; i <= sz; i ++) rk[i] = buf[idx(S[i]) - 1] + 1;
  for(int t = 1; t <= sz; t <<= 1) {
    for(int i = 1; i <= sz; i ++) {
      fir[i] = rk[i];
      sec[i] = (i + t > sz) ? 0 : rk[i + t];
    }
    std::fill(buf, buf + sz + 1, 0);
    for(int i = 1; i <= sz; i ++) buf[sec[i]] ++;
    for(int i = 1; i <= sz; i ++) buf[i] += buf[i - 1];
    for(int i = 1; i <= sz; i ++) tmp[buf[sec[i]] --] = i;

    std::fill(buf, buf + sz + 1, 0);
    for(int i = 1; i <= sz; i ++) buf[fir[i]] ++;
    for(int i = 1; i <= sz; i ++) buf[i] += buf[i - 1];
    for(int i = sz; i >= 1; i --) {
      int j = tmp[i];
      sa[buf[fir[j]] --] = j;
    }

    bool unique = true;
    for(int i = 1, las = 0; i <= sz; i ++) {
      int j = sa[i];
      if(!las) {
        rk[j] = 1;
      } else {
        if(fir[j] == fir[las] && sec[j] == sec[las]) {
          unique = false;
          rk[j] = rk[las];
        } else {
          rk[j] = rk[las] + 1;
        }
      }
      las = j;
    }
    if(unique) break;
  }
  for(int i = 1, k = 0; i <= sz; i ++) {
    if(rk[i] == 1) {
      k = 0;
    } else {
      if(k > 0) k --;
      int j = sa[rk[i] - 1];
      while(i + k <= sz && j + k <= sz && S[i + k] == S[j + k]) k ++;
    }
    height[rk[i]] = k;
  }
}
int s1, s2;
int solve() {
  process();
  int ans = 0;
  for(int i = 2; i <= sz; i ++) {
    int a = sa[i], b = sa[i - 1];
    bool v1 = a <= s1, v2 = b <= s1;
    if(v1 ^ v2) {
      ans = std::max(ans, height[i]);
    }
  }
  return ans;
}

int main() {
  scanf("%s", S + 1);
  s1 = strlen(S + 1);
  S[s1 + 1] = '$';
  scanf("%s", S + s1 + 2);
  sz = strlen(S + 1);
  printf("%d\n", solve());
  return 0;
}

POJ 1743 Musical Theme

Description

给一个由\([1, 88]\)中整数组成的数字串，要求取出两个长度相等的不重叠子串。要求：

  • 两个串的长度都大于5。
  • 一个子串可以通过整体加上一个整数得到另一个子串。

最大化取出子串的长度。

多组数据，串长不超过20000。

Solution

算事经典套路题了……一直知道但一直没做

首先第二个条件很鬼畜，我们考虑做一些转化搞掉它。我们直接把序列差分，这样的话除了第一项其他都能匹配（要考虑一下整个序列的第一项怎么处理啊，这个参考代码吧）。

先讲个比较逊的做法……很显然这个东西的答案具有单调性，那么考虑二分答案。

然后考虑该怎么判定答案。考虑当前二分答案为\(k\)，然后我们对于所有\(\mathrm{height}[i]\geq k\)，我们都可以合并\(\mathrm{sa}[i - 1]\)和\(\mathrm{sa}[i]\)（也就是说可能可以由这两个后缀产生答案，并且这种关系很显然具有传递性），那么就相当于除了\(\mathrm{height}[i] < k\)的情况被“断开”了，其他地方都已经分别连在一块了。那么每一块都是可能在块内产生答案（但不可能和块外产生答案），如果说某个块中最长后缀和最短后缀的差不小于\(k\)，那么说明该块可以取出两个不重叠的长度不小于\(k\)的后缀的前缀，因此\(k\)合法。反之\(k\)不合法。

这样复杂度很显然事\(O(n\log n)\)的，可以通过此题。

然后我们考虑那个二分答案其实不需要的……我们可以用并查集来维护块。我们每个块都维护块中最长后缀和最短后缀，刚开始每个点都是自己一块。从大到小枚举所有\(\mathrm{height}[i]\)的值，然后去合并块。每次合并出新的块的时候我们判一下是否有合法答案就行了。

Code

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
const int maxn = 200005;
int S[maxn]; int sz;
int sa[maxn], rk[maxn], height[maxn];
void process() {
  static int fir[maxn], sec[maxn];
  static int buf[maxn], tmp[maxn];
  std::fill(buf, buf + 1 + sz, 0);
  for(int i = 1; i <= sz; i ++) buf[S[i]] ++;
  for(int i = 1; i <= sz; i ++) buf[i] += buf[i - 1];
  for(int i = 1; i <= sz; i ++) rk[i] = buf[S[i] - 1] + 1;
  for(int t = 1; t <= sz; t <<= 1) {
    for(int i = 1; i <= sz; i ++) {
      fir[i] = rk[i];
      sec[i] = (i + t > sz) ? 0 : rk[i + t];
    }
    std::fill(buf, buf + sz + 1, 0);
    for(int i = 1; i <= sz; i ++) buf[sec[i]] ++;
    for(int i = 1; i <= sz; i ++) buf[i] += buf[i - 1];
    for(int i = 1; i <= sz; i ++) tmp[buf[sec[i]] --] = i;

    std::fill(buf, buf + sz + 1, 0);
    for(int i = 1; i <= sz; i ++) buf[fir[i]] ++;
    for(int i = 1; i <= sz; i ++) buf[i] += buf[i - 1];
    for(int i = sz; i >= 1; i --) {
      int j = tmp[i];
      sa[buf[fir[j]] --] = j;
    }

    bool unique = true;
    for(int i = 1, las = 0; i <= sz; i ++) {
      int j = sa[i];
      if(!las) {
        rk[j] = 1;
      } else {
        if(fir[j] == fir[las] && sec[j] == sec[las]) {
          unique = false;
          rk[j] = rk[las];
        } else {
          rk[j] = rk[las] + 1;
        }
      }
      las = j;
    }
    if(unique) break;
  }
  for(int i = 1, k = 0; i <= sz; i ++) {
    if(rk[i] == 1) {
      k = 0;
    } else {
      if(k > 0) k --;
      int j = sa[rk[i] - 1];
      while(i + k <= sz && j + k <= sz && S[i + k] == S[j + k]) k ++;
    }
    height[rk[i]] = k;
  }
}

int p[maxn], pd[maxn];
int minv[maxn], maxv[maxn];
void init_set() {
  for(int i = 1; i <= sz; i ++) {
    p[i] = i;
    minv[i] = maxv[i] = sa[i];
    pd[i] = 0;
  }
}
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return (p[x] = get_fa(p[x]));
  }
}
void link_set(int x, int y) {
  if(pd[x] > pd[y]) std::swap(x, y);
  p[x] = y;
  minv[y] = std::min(minv[y], minv[x]);
  maxv[y] = std::max(maxv[y], maxv[x]);
  if(pd[x] == pd[y]) pd[y] ++;
}
void merge_set(int x, int y) {
  x = get_fa(x), y = get_fa(y);
  if(x != y) link_set(x, y);
}

int solve() {
  static std::vector<int> V[maxn];
  process(); init_set();
  for(int i = 1; i <= sz; i ++) V[i].clear();
  for(int i = 2; i <= sz; i ++) {
#ifdef LOCAL
    printf("height[%d] : %d\n", i, height[i]);
#endif
    V[height[i]].push_back(i);
  }
  for(int i = sz; i >= 1; i --) {
    for(int j = 0; j < V[i].size(); j ++) {
      int u = V[i][j];
      merge_set(u - 1, u);
      u = get_fa(u);
      if(maxv[u] - minv[u] >= i) return i;
    }
  }
  return 0;
}

int main() {
  static int S2[maxn];
  S[0] = 50000;
  while(scanf("%d", &sz) == 1) {
    if(!sz) break;
    for(int i = 1; i <= sz; i ++) scanf("%d", &S[i]);
    for(int i = sz; i >= 1; i --) S[i] -= S[i - 1];
    std::copy(S + 1, S + 1 + sz, S2 + 1);
    std::sort(S2 + 1, S2 + 1 + sz);
    int lsiz = std::unique(S2 + 1, S2 + 1 + sz) - S2 - 1;
    for(int i = 1; i <= sz; i ++) {
      S[i] = std::lower_bound(S2 + 1, S2 + 1 + lsiz, S[i]) - S2;
    }
    int ret = solve() + 1;
    if(ret >= 5) {
      printf("%d\n", ret);
    } else {
      puts("0");
    }
  }
  return 0;
}

POJ 3415 Common Substrings

Description

给出两个串\(A,B\)和一个一个正整数\(k\)，求出两个串长度不小于\(k\)的公共子串的数量。

\(1\leq |A|,|B|\leq 10^5,1\leq k\leq\min(|A|,|B|)\)，多组数据。两个串最多由全体拉丁字母组成。

Solution

首先还是考虑把\(\mathrm{height}[i] < k\)的地方断开，剩下的地方连成块，然后剩下的每一块内部产生答案。

然后答案有两类，一类是在\(A\)中的后缀和排名比他小的\(B\)中的后缀产生答案，另一类情况是反过来的。那么会做第一类就会做第二类了。

考虑一个排名比\(i\)低的串，对\(i\)造成的贡献事两者的LCP再减\(k - 1\)，那么我们考虑怎么去维护所有串的贡献的和。我们注意到排名比\(\mathrm{sa}[i]\)越低，和\(\mathrm{sa}[i]\)的LCP就会越来越小，从左往右事单调递增的。所以我们可以用单调栈来维护这个东西。

Code

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <functional>
#include <utility>
#include <stack>
#include <vector>
int idx(char c) {
  if(c == '$') {
    return 53;
  } else if(c >= 'a' && c <= 'z') {
    return c - 'a' + 1;
  } else {
    return c - 'A' + 27;
  }
}

const int maxn = 200005;
char S[maxn]; int sz;
int sa[maxn], rk[maxn], height[maxn];
void process() {
  static int fir[maxn], sec[maxn];
  static int buf[maxn], tmp[maxn];
  std::fill(buf, buf + std::max(sz, 53) + 1, 0);
  for(int i = 1; i <= sz; i ++) buf[idx(S[i])] ++;
  for(int i = 1; i <= 53; i ++) buf[i] += buf[i - 1];
  for(int i = 1; i <= sz; i ++) rk[i] = buf[idx(S[i]) - 1] + 1;
  for(int t = 1; t <= sz; t <<= 1) {
    for(int i = 1; i <= sz; i ++) {
      fir[i] = rk[i];
      sec[i] = (i + t > sz) ? 0 : rk[i + t];
    }
    std::fill(buf, buf + sz + 1, 0);
    for(int i = 1; i <= sz; i ++) buf[sec[i]] ++;
    for(int i = 1; i <= sz; i ++) buf[i] += buf[i - 1];
    for(int i = 1; i <= sz; i ++) tmp[buf[sec[i]] --] = i;

    std::fill(buf, buf + sz + 1, 0);
    for(int i = 1; i <= sz; i ++) buf[fir[i]] ++;
    for(int i = 1; i <= sz; i ++) buf[i] += buf[i - 1];
    for(int i = sz; i >= 1; i --) {
      int j = tmp[i];
      sa[buf[fir[j]] --] = j;
    }

    bool unique = true;
    for(int i = 1, las = 0; i <= sz; i ++) {
      int j = sa[i];
      if(!las) {
        rk[j] = 1;
      } else {
        if(fir[j] == fir[las] && sec[j] == sec[las]) {
          unique = false;
          rk[j] = rk[las];
        } else {
          rk[j] = rk[las] + 1;
        }
      }
      las = j;
    }
    if(unique) break;
  }
  for(int i = 1, k = 0; i <= sz; i ++) {
    if(rk[i] == 1) {
      k = 0;
    } else {
      if(k > 0) k --;
      int j = sa[rk[i] - 1];
      while(i + k <= sz && j + k <= sz && S[i + k] == S[j + k]) k ++;
    }
    height[rk[i]] = k;
  }
}
int s1, s2;
bool check(int i) {
  return (i <= s1);
}
struct Node {
  int cnt, val;
  Node(int v, int c = 1) {
    val = v; cnt = c;
  }
  bool operator <(const Node &res) const {
    return val < res.val;
  }
  bool operator ==(const Node &res) const {
    return val == res.val;
  }
  bool operator >(const Node &res) const {
    return val > res.val;
  }
};
int k;
typedef long long ll;
struct DStack {
  std::stack<Node> S;
  ll ans;
  DStack() { ans = 0; }
  void clear() {
    ans = 0;
    while(!S.empty()) S.pop();
  }
  void insert(Node x) {
    while(!S.empty() && (S.top() > x || S.top() == x)) {
      ll v = S.top().val, c = S.top().cnt; S.pop();
      ans -= v * c; x.cnt += c;
    }
    S.push(x); ans += (ll(x.cnt)) * (ll(x.val));
  }
};

ll solve(bool bs) {
  DStack S;
  ll ans = 0;
  for(int i = 1; i <= sz; i ++) {
    if(height[i] < k) {
      S.clear(); continue;
    }
    bool th = check(sa[i]);
    S.insert(Node(height[i] - k + 1, (check(sa[i - 1]) != bs) ? 1 : 0));
    if(th == bs) ans += S.ans;
  }
  return ans;
}

int main() {
  while(scanf("%d", &k) == 1) {
    if(!k) break;
    scanf("%s", S + 1);
    s1 = strlen(S + 1);
    S[s1 + 1] = '$';
    scanf("%s", S + 2 + s1);
    sz = strlen(S + 1);
#ifdef LOCAL
    printf("s1 : %d\nsz : %d\n", s1, sz);
    puts(S + 1);
#endif
    process();
    printf("%lld\n", solve(false) + solve(true));
  }
  return 0;
}

LibreOJ 2059 「TJOI / HEOI2016」字符串

Description

给出一个长度为\(n\)的小写字母串\(S\)，\(m\)询问\(a, b, c, d\)，求出\(S[a\ldots b]\)的所有子串和\(S[c\ldots d]\)本身的LCP的最大值。

\(1\leq n, m\leq 10^5, 1\leq a\leq b\leq n, 1\leq c\leq d\leq n\)。

Solution

很显然这个东西的答案满足单调性……所以我们就二分答案吧。

那么考虑怎么判定呢。 假设当前二分出来的答案为\(k\)，那么和后缀\(c\ldots n\)的LCP为\(k\)的后缀在后缀数组中一定为一段区间（假设为\([l, r]\)），那么如果这段区间里有个\(i\)满足\(\mathrm{sa}[i]\in[a, b - k + 1]\)，那么显然答案合法，反之则不合法。

于是我们队后缀数组建主席树，然后每次判定就是确定\([l, r]\)（这个也可以二分答案搞）之后在一段区间里查询是否有值在一段区间里的位置就行了。

Code

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <functional>
#include <utility>
int idx(char c) {
  if(c == '$') {
    return 27;
  } else {
    return c - 'a' + 1;
  }
}

const int maxn = 100005;
char S[maxn]; int sz;
int sa[maxn], rk[maxn], height[maxn];
void process() {
  static int fir[maxn], sec[maxn];
  static int buf[maxn], tmp[maxn];
  std::fill(buf, buf + 28, 0);
  for(int i = 1; i <= sz; i ++) buf[idx(S[i])] ++;
  for(int i = 1; i <= 27; i ++) buf[i] += buf[i - 1];
  for(int i = 1; i <= sz; i ++) rk[i] = buf[idx(S[i]) - 1] + 1;
  for(int t = 1; t <= sz; t <<= 1) {
    for(int i = 1; i <= sz; i ++) {
      fir[i] = rk[i];
      sec[i] = (i + t > sz) ? 0 : rk[i + t];
    }
    std::fill(buf, buf + sz + 1, 0);
    for(int i = 1; i <= sz; i ++) buf[sec[i]] ++;
    for(int i = 1; i <= sz; i ++) buf[i] += buf[i - 1];
    for(int i = 1; i <= sz; i ++) tmp[buf[sec[i]] --] = i;

    std::fill(buf, buf + sz + 1, 0);
    for(int i = 1; i <= sz; i ++) buf[fir[i]] ++;
    for(int i = 1; i <= sz; i ++) buf[i] += buf[i - 1];
    for(int i = sz; i >= 1; i --) {
      int j = tmp[i];
      sa[buf[fir[j]] --] = j;
    }

    bool unique = true;
    for(int i = 1, las = 0; i <= sz; i ++) {
      int j = sa[i];
      if(!las) {
        rk[j] = 1;
      } else {
        if(fir[j] == fir[las] && sec[j] == sec[las]) {
          unique = false;
          rk[j] = rk[las];
        } else {
          rk[j] = rk[las] + 1;
        }
      }
      las = j;
    }
    if(unique) break;
  }
  for(int i = 1, k = 0; i <= sz; i ++) {
    if(rk[i] == 1) {
      k = 0;
    } else {
      if(k > 0) k --;
      int j = sa[rk[i] - 1];
      while(i + k <= sz && j + k <= sz && S[i + k] == S[j + k]) k ++;
    }
    height[rk[i]] = k;
  }
}

int minv[maxn][18], lim[maxn];
void process_st() {
  for(int i = 1; i <= sz; i ++) {
    minv[i][0] = height[i];
  }
  for(int j = 1; (1 << j) <= sz; j ++) {
    for(int i = 1; (i + (1 << j) - 1) <= sz; i ++) {
      minv[i][j] = std::min(minv[i][j - 1], minv[i + (1 << (j - 1))][j - 1]);
    }
  }
  for(int i = 1; i <= sz; i ++) {
    int v = 0;
    while((1 << (v + 1)) <= i) v ++;
    lim[i] = v;
  }
}
int query(int l, int r) {
  if(l > r) return 0x7fffffff;
  int c = lim[r - l + 1];
  return std::min(minv[l][c], minv[r - (1 << c) + 1][c]);
}

const int bufsiz = 100 * 1024 * 1024;
char buf[bufsiz]; char *cur = buf;
void *alloc(size_t size) {
  if(buf - cur + size > bufsiz) {
    return malloc(size);
  } else {
    char *ret = cur; cur += size;
    return ret;
  }
}

struct Node {
  Node *lc, *rc;
  int sumv;
};
Node *nil;
void init_pool() {
  nil = (Node*)alloc(sizeof(Node));
  nil -> sumv = 0;
  nil -> lc = nil -> rc = nil;
}
Node *alloc_node(int v = 0, Node *lc = nil, Node *rc = nil) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> sumv = v;
  ret -> lc = lc; ret -> rc = rc;
  return ret;
}
Node *modify(Node *o, int L, int R, int p, int v) {
  Node *ret = alloc_node(o -> sumv + v, o -> lc, o -> rc);
  if(L < R) {
    int M = (L + R) / 2;
    if(p <= M) {
      ret -> lc = modify(ret -> lc, L, M, p, v);
    } else {
      ret -> rc = modify(ret -> rc, M + 1, R, p, v);
    }
  }
  return ret;
}
int query(Node *o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return o -> sumv;
  } else {
    int ans = 0;
    int M = (L + R) / 2;
    if(ql <= M) ans += query(o -> lc, L, M, ql, qr);
    if(qr > M) ans += query(o -> rc, M + 1, R, ql, qr);
    return ans;
  }
}
Node *T[maxn];
int query(int lt, int rt, int l, int r) {
  return query(T[rt], 1, sz, l, r) - query(T[lt - 1], 1, sz, l, r);
}
void process_tree() {
  init_pool();
  T[0] = nil;
  for(int i = 1; i <= sz; i ++) {
    T[i] = modify(T[i - 1], 1, sz, sa[i], 1);
  }
#ifdef LOCAL
  puts("Processing tree ended!"); fflush(stdout);
#endif
}

bool check(int x, int c, int l, int r) {
  int L, R, lp = c, rp = c;
  L = 1, R = c - 1;
  while(true) {
    if(R - L <= 3) {
      for(int i = L; i <= R; i ++) {
        if(query(i + 1, c) >= x) {
          lp = i; break;
        }
      }
      break;
    }
    int M = (L + R) / 2;
    if(query(M + 1, c) >= x) {
      R = M;
    } else {
      L = M;
    }
  }
  L = c + 1, R = sz;
  while(true) {
#ifdef LOCAL
    printf("CState (%d, %d)\n", L, R); fflush(stdout);
#endif
    if(R - L <= 3) {
      for(int i = R; i >= L; i --) {
        if(query(c + 1, i) >= x) {
          rp = i; break;
        }
      }
      break;
    }
    int M = (L + R) / 2;
    if(query(c + 1, M) >= x) {
      L = M;
    }else {
      R = M;
    }
  }
#ifdef LOCAL
  printf("%d : [%d, %d]\n", c, lp, rp); fflush(stdout);
#endif
  return (query(lp, rp, l, r) > 0);
}
int solve(int a, int b, int c, int d) {
  int L = 1, R = std::min(d - c + 1, b - a + 1);
  int ret = 0;
  while(true) {
#ifdef LOCAL
    printf("State (%d, %d)\n", L, R); fflush(stdout);
#endif
    if(R - L <= 3) {
      for(int i = R; i >= L; i --) {
        if(check(i, rk[c], a, b - i + 1)) {
          ret = i; break;
        }
      }
      break;
    }
    int M = (L + R) / 2;
    if(check(M, rk[c], a, b - M + 1)) {
      L = M;
    } else {
      R = M;
    }
  }
  return ret;
}

int main() {
  int q; scanf("%d%d%s", &sz, &q, S + 1);
  process(); process_st(); process_tree();
  while(q --) {
    int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
    printf("%d\n", solve(a, b, c, d));
  }
  return 0;
}

后缀自动机

介绍

还在路上，马上就来了（鸽并感）

题目

例题1

Description

给一个字母串，求出它的最小表示法（就是可以进行若干次循环位移，使得串的字典序尽可能小）。

\(n\leq 10^{5}\)。

Solution

把串复制两份接一块，那么很显然就是要求新串的一个长度为\(n\)的子串，使得这个串的字典序最小。

那么考虑建新串的后缀自动机。从根开始每一步走尽可能小的转移边即可。

LibreOJ 2033 「SDOI2016」生成魔咒

Description

有一个初始为空的整数串\(S\)，要求动态的往尾部加数，每次操作完后求数字串的本质不同子串数目。

操作次数不超过十万次，\(S\)中的数在\([1, 10^9]\)中。

Solution

参考原博客

SPOJ NSUBSTR

Description

给一个字符串\(S\)，用\(F(x)\)表示所有\(S\)的长度为\(x\)的子串中出现次数的最大值。求\(F(1)\ldots F(|S|)\)。

\(|S|\leq 250000\)。

Solution

参考原博客

SPOJ LCS2

Description

给你至多十个串，求他们的最长公共子串。

每个串的大小不超过十万。

Solution

参考原博客

LibreOJ 2102 「TJOI2015」弦论

Description

对于一个长为\(n\)的小写字母串\(S\)，求它的第\(k\)小子串。

每组数据还给定一个\(T\)，表示对于不同位置的相同子串是否算一种。

\(n\leq 5\times 10^5, k\leq 10^9\)。

Solution

参考原博客

LibreOJ 2137 「ZJOI2015」诸神眷顾的幻想乡

Description

给出一个点上写着字符（这里字符定义为小于\(c\)的自然数）的树，度数为1的点的数量不超过20。定义其子串为从一个点延最短路走到另一个点（显然方案唯一），把经过的点上的字符顺次写下来所得到的字符串。

求这棵树有多少种本质不同子串。

\(1\leq n\leq 10^5, 1\leq c\leq 10\)。

Solution

参考原博客