0%

字符串

字符串的板子们。

最小表示法

OI Wiki

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
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fl first
#define fr second
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 300000 + 5;

int Get(int *s, int n)
{
int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n)
{
if (s[(i + k) % n] == s[(j + k) % n]) k++;
else
{
if (s[(i + k) % n] > s[(j + k) % n]) i = i + k + 1;
else j = j + k + 1;
if (i == j) i++;
k = 0;
}
}
return min(i, j);
}

int n, a[N];

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int k = Get(a + 1, n) + 1;
for (int i = k; i <= n; i++) printf("%d ", a[i]);
for (int i = 1; i < k; i++) printf("%d ", a[i]);
return 0;
}

Lyndon 分解

OI Wiki

Lyndon 串:对于字符串 $s$ ,如果 $s$ 的字典序严格小于 $s$ 的所有后缀的字典序,我们称 $s$ 是 Lyndon 串。$s$ 是 Lyndon 串,当且仅当 $s$ 的字典序严格小于它的所有非平凡的循环同构串。

Lyndon 分解:串 $s$ 的 Lyndon 分解记为 $s=w_1w_2\cdots w_k$ ,其中所有 $w_i$ 为简单串,并且他们的字典序按照非严格单减排序,即 $w_1\ge w_2\ge\cdots\ge w_k$ 。可以发现,这样的分解存在且唯一。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 5e6 + 5;

int n;
char s[N];

int Duval()
{
int ans = 0, i = 0;
while (i < n)
{
int j = i + 1, k = i;
while (j < n && s[k] <= s[j])
{
if (s[k] < s[j]) k = i;
else k++;
j++;
}
while (i <= k) i += j - k, ans ^= i;
}
return ans;
}

int main()
{
scanf("%s", s);
n = strlen(s);
printf("%d\n", Duval());
return 0;
}