「算法学习」runs

学习 / 字符串
Word count: 2k   |   Reading time≈ 10 min

简 单 的 广 场

Description

定义一个字符串 $|S|$ 里的一个 run，指其内部的一端两侧都不能扩展的周期子串，且周期至少完整出现两次。

严格地说，一个 run 是一个三元组 $(i, j, p)$ ，满足 $p$ 是 $S[i\dots j]$ 的最小周期， $j - i +1 \geq 2p$ ，且满足如下两个条件：

  • 要么 $i = 1$，要么 $S[i - 1] \ne S[i - 1 + p]$ ；
  • 要么 $j = n$，要么 $S[j + 1] \ne S[j +1 - p]$。

给定字符串 $S$ ，求他的所有 runs。

Solution

具体证明可能要去把一整个集训队论文都抄下来，但是我是条懒狗，所以就跳过了，这里主要还是讲一下如何求 runs。虽然 runs 有一个很优美的 $O(n)$ 求法，但是👴8会，这里讲另一个 simple 做法。

有一个结论是，对于一个 run $(i, j, p)$ ，他的最小周期一定是一个 lyndon 串，为什么？因为对于一个run，我们要求他至少包含了两次周期，也就是包含了这个周期的所有循环排列，毛估估一下，至少有一个是 lyndon 串。于是我们可以先求出这个串 lyndon array（这里实现的时候你可能要把两种定义的lyndon都求出来，无论是大于还是小于，具体为什么我不懂），然后对于每个 lyndon 往左往右扩展一下，具体实现的时候可以写个 lcp 和 lcs，求出来之后把那些长度比循环两倍要小的串 ban 了，然后把重复的串也 ban 了，子串相同的串只留下循环最小的那个，剩下的那些就是这个串的 runs 了。具体实现的时候可以写两个 SA 求任意两个串的 lcp 和 lcs，然后用 rk 数组和单调栈求出 lyndon array，但是如果题目除了这部分就用不到 SA 了，那大可写个二分 + hash ，因为这个算法中比较字符串字典序的总次数是 O(n)，而求 lcp 和 lcs 就是二分 + hash 的天职。如果你够咍，可以写 SA-IS，那也是 O(n)，记得学会了之后顺便教一下我，因为我事真滴8会。

不过求出 runs 并没有什么用，我们更多的是关心他的性质。首先 runs 有一个很好的性质，就是一个串的 runs 的长度和是 $O(n\log{n})$ 的，因为每个 run 的一个前缀都一一对应一个本源平方串，而本源平方串的个数可以证明是 $O(n\log{n})$。因为 runs 的长度之和得到了保证，也就意味着对于一些特殊的题目，循环串会产生贡献，我们可以把那些循环相同的串放一起算，求出 runs 之后用前缀和之类的数据结构维护，复杂度就是 $O(n\log{n})$ 左右，当然 runs 还有很多性质，本人也就是刚刚入门罢了，具体的应用会在日后研究。

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
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define int long long
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (ll i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter putchar('\n')
#define siz(x) ((ll)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <ll, ll> pii ;
typedef vector <ll> vi ;
typedef vector <pii> vii ;
typedef queue <ll> qi ;
typedef queue <pii> qii ;
typedef set <ll> si ;
typedef map <ll, ll> mii ;
typedef map <string, ll> msi ;
const ll maxn = 2e6 + 100 ;
const ll inf = 0x3f3f3f3f ;
const ll iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 998244353 ;
const double eps = 1e-7 ;
template <class T = ll> T chmin(T &a, T b) { return a = min(a, b);}
template <class T = ll> T chmax(T &a, T b) { return a = max(a, b);}
template <class T = ll> T read()
{
    T f = 1, a = 0;
    char ch = getchar() ;
    while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
    while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
    return a * f ;
}

char s[maxn];

ll n;

ll sa[maxn], rk[maxn], x[maxn], y[maxn], c[maxn];

void get_sa()
{
    ll m = 114514;
    rep(i, 1, m) c[i] = 0;
    rep(i, 1, n) c[x[i] = s[i]] ++;
    rep(i, 1, m) c[i] += c[i - 1];
    per(i, n, 1) sa[c[x[i]] --] = i;
    for(ll k = 1; k <= n; k <<= 1)
    {
        ll num = 0;
        rep(i, n - k + 1, n) y[++ num] = i;
        rep(i, 1, n) if(sa[i] > k) y[++ num] = sa[i] - k;
        rep(i, 1, m) c[i] = 0;
        rep(i, 1, n) c[x[i]] ++;
        rep(i, 1, m) c[i] += c[i - 1];
        per(i, n, 1) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
        swap(x, y);
        num = x[sa[1]] = 1;
        rep(i, 2, n) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if(num == n) break ;
        m = num;
    }
    rep(i, 1, n) rk[sa[i]] = i;
}

ll h[maxn];

void get_height(char *s, ll n)
{
    ll pos = 0;
    rep(i, 1, n)
    {
        if(pos) pos --;
        while(s[i + pos] == s[sa[rk[i] - 1] + pos]) pos ++;
        h[rk[i]] = pos;
    }
}


ll st[maxn][21], lg[maxn];

void st_init()
{
    rep(i, 1, n) st[i][0] = h[i];
    rep(j, 1, 20) rep(i, 1, n) st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    ll tmp = 0;
    rep(i, 1, n)
    {
        if((1 << (tmp + 1)) < i) tmp ++;
        lg[i] = tmp;
    }
}

ll query_lcp(ll l, ll r)
{
    ll len = r - l + 1;
    return min(st[l][lg[len]], st[r - (1 << lg[len]) + 1][lg[len]]);
}

ll get_lcp(ll l, ll r)
{
    l = rk[l], r = rk[r];
    if(l > r) swap(l, r);
    return query_lcp(l + 1, r);
}

ll lyd[2][maxn];

ll sta[maxn], top;

void get_lyd()
{
    rep(i, 1, n)
    {
        while(top && rk[sta[top]] > rk[i]) lyd[0][sta[top]] = i - 1, top --;
        sta[++ top] = i;
    }
    while(top) lyd[0][sta[top]] = n, top --;
    rep(i, 1, n)
    {
        while(top && (n - rk[sta[top]]) > (n - rk[i]))
        {
            ll lcp = query_lcp(rk[sta[top]] + 1, rk[i]);
            // printf("query_lcp : %lld %lld %lld\n", sta[top], i, lcp);
            if(lcp == n - i + 1) break;
            lyd[1][sta[top]] = i - 1, top --;
        }
        sta[++ top] = i;
    }
    while(top) lyd[1][sta[top]] = n, top --;
}

ll tot, cnt;

ll vis[maxn];

pair <pii, ll> runs[maxn], tmp[maxn];

void get_runs()
{
    rep(k, 0, 1)
    {
        rep(i, 1, n)
        {
            // printf("i : %lld\n", i);
            ll l = i, r = lyd[k][i], len = r - l + 1;
            r = r + get_lcp(r + 1, l);
            ll tl = 1, tr = l - 1;
            while(tl <= tr)
            {
                ll mid = (tl + tr) >> 1;
                ll tmp = i - mid;
                if(get_lcp(mid, lyd[k][i] - tmp + 1) >= tmp) l = mid, tr = mid - 1;
                else tl = mid + 1;
            }
            // printf("%lld : %lld %lld %lld\n", i, l, r, len);
            if(r - l + 1 >= len * 2) runs[++ tot] = mp(mp(l, r), len);
        }
    }
}

signed main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1), get_sa(), get_height(s, n), st_init(), get_lyd(), get_runs();
    // rep(i, 1, n) printf("%lld %lld\n", lyd[0][i], lyd[1][i]);
    sort(runs + 1, runs + tot + 1);
    ll lastl = 0, lastr = 0;
    rep(i, 1, tot)
    {
        if(runs[i].fi.fi == lastl && runs[i].fi.se == lastr) ;
        else lastl = runs[i].fi.fi, lastr = runs[i].fi.se, tmp[++ cnt] = runs[i];
    }
    tot = cnt;
    swap(tmp, runs);
    printf("%lld\n", tot);
    rep(i, 1, tot) printf("%lld %lld %lld\n", runs[i].fi.fi, runs[i].fi.se, runs[i].se);
    return 0;
}

postscript

当时学 runs 的时候看了看别人的博客，发现了一个词叫做 Primitive squares，去翻译的一下，这个东西叫简单的广场，想了一会没想通，后面问了问同学，原来是本源平方串的意思，感觉这个翻译过于迫击炮，仿佛就是👽诡计。

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 naitir
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信