「字符串系列」

后缀数组

讲解地址 : 戳这里
模板地址 : 戳这里

后缀数组一·重复旋律

描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 $N$ 的数构成的数列。
小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。旋律是一段连续的数列,相似的旋律在原数列可重叠。比如在$1 2 3 2 3 2 1$ 中 $2 3 2$ 出现了两次。
小Hi想知道一段旋律中出现次数至少为$K$次的旋律最长是多少?
输入
第一行两个整数 $N$和$K$。$1≤N≤20000 1≤K≤N$
接下来有 $N$ 个整数,表示每个音的数字。$1≤数字≤100$
输出
一行一个整数,表示答案。
样例输入

8 2
1 2 3 2 3 2 3 1

样例输出

4

题解
利用 $Height$ 数组(表示第 排名为 $i$ 的后缀与排名为 $i - 1$ 的后缀的最长公共前缀)即可高效求解
可以选择结合 $O(n)$ 的单调队列或者是 $O(nlogn)$ 的 $RMQ$ 求解

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
#include <iostream>
#include <cstring>
#include <cstdio>
const int maxn = 1e6 + 10;
int n, m, SA[maxn], Rank[maxn], Height[maxn], tmp[maxn], Tax[maxn];
int str[maxn];
void Rsort() {
for (register int i = 0; i <= m; i++) Tax[i] = 0;
for (register int i = 1; i <= n; i++) Tax[Rank[i]]++;
for (register int i = 1; i <= m; i++) Tax[i] += Tax[i - 1];
for (register int i = n; i; i--) SA[Tax[Rank[tmp[i]]]--] = tmp[i];
}
bool cmp(int *f, int x, int y, int w) {
return f[x] == f[y] && (x + w <= n ? f[x + w] : 0) == (y + w <= n ? f[y + w] : 0);
}
void Suffix() {
for (int i = 1; i <= n; i++) Rank[i] = int(str[i - 1]), tmp[i] = i;
m = 256; Rsort();
for (register int p = 1, w = 1, i; p < n; w <<= 1, m = p) {
for (p = 0, i = n - w + 1; i <= n; i++) tmp[++p] = i;
for (i = 1; i <= n; i++) if (SA[i] > w) tmp[++p] = SA[i] - w;
Rsort(); std::swap(Rank, tmp); Rank[SA[1]] = p = 1;
for (i = 2; i <= n; i++) Rank[SA[i]] = cmp(tmp, SA[i], SA[i - 1], w) ? p : ++p;
}
int j, k = 0;
for (int i = 1; i <= n; Height[Rank[i]] = k, i++)
for (k = (k ? k - 1 : k), j = SA[Rank[i] - 1]; str[i + k - 1] == str[j + k - 1]; k++);
}
int que[maxn], head, tail;
int main() {
int k; scanf("%d%d", &n, &k);
if (k == 1) return 0 * printf("%d\n", n);
for (int i = 0; i < n; i++) scanf("%d", &str[i]);
Suffix(); head = 1; tail = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
while (head <= tail && Height[i] <= Height[que[tail]]) tail--;
while (head <= tail && i - que[head] + 2 > k) head++;
que[++tail] = i; ans = std::max(ans, Height[que[head]]);
}
printf("%d\n", ans);
}

后缀数组二·重复旋律2

描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。
旋律可以表示为一段连续的数列,相似的旋律在原数列不可重叠,比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次,2 3 出现了两次,小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少?
输入
第一行一个整数 $N$。$1≤N≤100000$

接下来有 $N$ 个整数,表示每个音的数字。$1≤数字≤1000$
输出

一行一个整数,表示答案。
样例输入

8
1 2 3 2 3 2 3 1

样例输出

2

题解
二分答案$ans$,将 $Height$ 连续大于该 $ans$ 的后缀划分为一组,然后检查这一组中 $SA$ 最最大的和最小的两个串,看看是否重叠即可

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
#include <bits/stdc++.h>
const int maxn = 1e6;
namespace Suffix {
int SA[maxn], Rank[maxn], Height[maxn], str[maxn], tmp[maxn], Tax[maxn];
void init(int n) {
for (int i = 1; i <= n; i++) scanf("%d", &str[i]);
}
void sort(int n, int m) {
for (int i = 0; i <= m; i++) Tax[i] = 0;
for (int i = 1; i <= n; i++) Tax[Rank[i]]++;
for (int i = 1; i <= m; i++) Tax[i] += Tax[i - 1];
for (int i = n; i; i--) SA[Tax[Rank[tmp[i]]]--] = tmp[i];
}
bool cmp(int *f, int x, int y, int w, int n) {
return f[x] == f[y] && (x + w > n ? 0 : f[x + w]) == (y + w > n ? 0 : f[y + w]);
}
void build(int n) {
init(n);
for (int i = 1; i <= n; i++) Rank[i] = str[i], tmp[i] = i;
int m = 1000; sort(n, m);
for (int i, w = 1, p = 1; p < n; m = p, w <<= 1) {
for (p = 0, i = n - w + 1; i <= n; i++) tmp[++p] = i;
for (i = 1; i <= n; i++) if (SA[i] > w) tmp[++p] = SA[i] - w;
sort(n, m); std::swap(Rank, tmp); Rank[SA[1]] = p = 1;
for (i = 2; i <= n; i++) Rank[SA[i]] = cmp(tmp, SA[i], SA[i - 1], w, n) ? p : ++p;
}
int j, k = 0;
for (int i = 1; i <= n; Height[Rank[i]] = k, i++)
for (k = (k ? k - 1 : k), j = SA[Rank[i] - 1]; str[i + k] == str[j + k]; k++);
}
}
using namespace Suffix;
int n;
bool check(int ans) {
for (int i = 2, j; i <= n; i = j) {
for (j = i + 1; Height[j] >= ans && j <= n; j++);
int maxp = SA[i] - 1, minp = SA[i] - 1;
for (int k = i; k != j; k++)
maxp = std::max(maxp, SA[k]), minp = std::min(minp, SA[k]);
if (maxp - minp >= ans) return true;
}
return false;
}
int main() {
scanf("%d", &n); Suffix::build(n);
int l = 0, r = n;
while (l < r) {
int mid = (l + r >> 1) + 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", l);
}

后缀数组三·重复旋律3

描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。
旋律是一段连续的数列,如果同一段旋律在作品A和作品B中同时出现过,这段旋律就是A和B共同的部分,比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少?
输入
共两行。一行一个仅包含小写字母的字符串。字符串长度不超过 100000。
输出
一行一个整数,表示答案。
样例输入

abcdefg
abacabca

样例输出

3

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
#include <bits/stdc++.h>
const int maxn = 3e6;
char s[maxn];
namespace SuffixArray {
int SA[maxn], Height[maxn], Rank[maxn], tmp[maxn], str[maxn], tax[maxn];
void init(int n) {
for (int i = 1; i <= n; i++) str[i] = s[i - 1];
}
void sort(int n, int m) {
memset(tax, 0, sizeof(int) * (m + 1));
for (int i = 1; i <= n; i++) tax[Rank[i]]++;
for (int i = 1; i <= m; i++) tax[i] += tax[i - 1];
for (int i = n; i; i--) SA[tax[Rank[tmp[i]]]--] = tmp[i];
}
inline bool cmp(int *f, int x, int y, int w, int n) {
return f[x] == f[y] && (x + w > n ? -1 : f[x + w]) == (y + w > n ? -1 : f[y + w]);
}
void build(int n) {
init(n);
for (int i = 1; i <= n; i++) Rank[i] = str[i], tmp[i] = i;
int m = 256; sort(n, m);
for (int i, p = 1, w = 1; p < n; m = p, w <<= 1) {
for (p = 0, i = n - w + 1; i <= n; i++) tmp[++p] = i;
for (i = 1; i <= n; i++) if (SA[i] > w) tmp[++p] = SA[i] - w;
sort(n, m); std::swap(Rank, tmp); Rank[SA[1]] = p = 1;
for (i = 2; i <= n; i++) Rank[SA[i]] = cmp(tmp, SA[i], SA[i - 1], w, n) ? p : ++p;
}
int j, k = 0;
for (int i = 1; i <= n; Height[Rank[i++]] = k)
for (k = (k ? k - 1 : k), j = SA[Rank[i] - 1]; str[i + k] == str[j + k]; k++);
}
}
using namespace SuffixArray;
int main() {
scanf("%s", s);
int n = strlen(s);
s[n] = '$';
scanf("%s", s + n + 1);
int m = strlen(s);
build(m); int ans = 0;
for (int i = 2; i <= m; i++) {
if (SA[i] <= n && SA[i - 1] > n + 1) ans = std::max(ans, Height[i]);
if (SA[i] > n + 1 && SA[i - 1] <= n) ans = std::max(ans, Height[i]);
}
printf("%d\n", ans);
}

后缀数组四·重复旋律4

描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。
我们把一段旋律称为(k,l)-重复的,如果它满足由一个长度为l的字符串重复了k次组成。 如旋律abaabaabaaba是(4,3)重复的,因为它由aba重复4次组成。
小Hi想知道一部作品中k最大的(k,l)-重复旋律。
输入
一行一个仅包含小写字母的字符串。字符串长度不超过 100000。
输出
一行一个整数,表示答案k。
样例输入

babbabaabaabaabab

样例输出

4

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
#include <bits/stdc++.h>
const int maxn = 1e6 + 10;
namespace SuffixArray {
int SA[maxn], Rank[maxn], Height[maxn], tmp[maxn], tax[maxn];
char str[maxn];
void sort(int n, int m) {
memset(tax, 0, sizeof(int) * (m + 1));
for (int i = 1; i <= n; i++) tax[Rank[i]]++;
for (int i = 1; i <= m; i++) tax[i] += tax[i - 1];
for (int i = n; i; i--) SA[tax[Rank[tmp[i]]] --] = tmp[i];
}
bool cmp(int *f, int x, int y, int w, int n) {
return f[x] == f[y] && (x + w > n ? -1 : f[x + w]) == (y + w > n ? -1 : f[y + w]);
}
void build(int n) {
for (int i = 1; i <= n; i++) Rank[i] = str[i], tmp[i] = i;
int m = 128; sort(n, m);
for (int i, w = 1, p = 1; p < n; m = p, w <<= 1) {
for (p = 0, i = n - w + 1; i <= n; i++) tmp[++p] = i;
for (i = 1; i <= n; i++) if (SA[i] > w) tmp[++p] = SA[i] - w;
sort(n, m);
for (i = 1; i <= n; i++) tmp[i] = Rank[i];
for (Rank[SA[1]] = p = 1, i = 2; i <= n; i++)
Rank[SA[i]] = cmp(tmp, SA[i], SA[i - 1], w, n) ? p : ++p;
}
for (int i = 1, j, k = 0; i <= n; Height[Rank[i++]] = k)
for (k = (k ? k - 1 : k), j = SA[Rank[i] - 1]; str[i + k] == str[j + k]; k++);
}
}
namespace SpraseTable {
int minv[maxn][22];
void build(int *a, int n) {
for (int i = 1; i <= n; i++) minv[i][0] = a[i];
for (int j = 1; j <= 21; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
minv[i][j] = std::min(minv[i][j - 1], minv[i + (1 << (j - 1))][j - 1]);
}
int query(int l, int r) {
int k = log2(r - l + 1);
return std::min(minv[l][k], minv[r - (1 << k) + 1][k]);
}
}
int lcp(int x, int y) {
x = SuffixArray::Rank[x];
y = SuffixArray::Rank[y];
if (x > y) std::swap(x, y);
return SpraseTable::query(x + 1, y);
}
int ans = 0;
int main() {
scanf("%s", SuffixArray::str + 1);
int n = strlen(SuffixArray::str + 1);
SuffixArray::build(n);
SpraseTable::build(SuffixArray::Height, n);
for (int L = 1; L <= n; L++)
for (int i = 1; i + L <= n; i += L) {
int R = lcp(i, i + L);
ans = std::max(ans, R / L + 1);
if (i - L + R % L >= 1) {
ans = std::max(ans, lcp(i - L + R % L, i + R % L) / L + 1);
}
}
printf("%d\n", ans);
}

后缀自动机二·重复旋律5

描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。
现在小Hi想知道一部作品中出现了多少不同的旋律?
输入
共一行,包含一个由小写字母构成的字符串。字符串长度不超过 1000000。
输出
一行一个整数,表示答案。
样例输入

aab

样例输出

5

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
#include <bits/stdc++.h>
const int maxn = 2e6 + 10;
namespace SuffixAutomation {
struct node {
int minlen, maxlen, trans[26], slink;
}T[maxn]; int nodeCnt;
int newnode(int maxlen, int minlen, int* trans, int slink) {
T[nodeCnt].maxlen = maxlen;
T[nodeCnt].minlen = minlen;
T[nodeCnt].slink = slink;
if (trans != NULL)
for (int i = 0; i < 26; i++) T[nodeCnt].trans[i] = trans[i];
else
for (int i = 0; i < 26; i++) T[nodeCnt].trans[i] = -1;
return nodeCnt++;
}
int addchar(char ch, int u) {
int c = ch - 'a', v = u;
int z = newnode(T[u].maxlen + 1, -1, NULL, -1);
while (v != -1 && T[v].trans[c] == -1)
T[v].trans[c] = z, v = T[v].slink;
if (v == -1) {
T[z].minlen = 1; T[z].slink = 0; return z;
}
int x = T[v].trans[c];
if (T[v].maxlen + 1 == T[x].maxlen) {
T[z].slink = x; T[z].minlen = T[x].maxlen + 1; return z;
}
int y = newnode(T[v].maxlen + 1, -1, T[x].trans, T[x].slink);
T[z].minlen = T[x].minlen = T[y].maxlen + 1;
T[z].slink = T[x].slink = y;
int w = v;
while (w != -1 && T[w].trans[c] == x)
T[w].trans[c] = y, w = T[w].slink;
T[y].minlen = T[T[y].slink].maxlen + 1;
return z;
}
void build(char *s) {
newnode(0, 0, 0, -1);
for (int i = 0, j = 0; s[i]; i++)
j = addchar(s[i], j);
}
}
using namespace SuffixAutomation;
char s[maxn];
int main() {
//freopen("data.txt", "r", stdin);
scanf("%s", s); build(s);
long long ans = 0;
for (int i = 1; i < nodeCnt; i++)
ans = ans + T[i].maxlen - T[i].minlen + 1;
printf("%lld", ans);
}

后缀自动机三·重复旋律6

描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。
现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的,小Hi想知道对于所有的K的答案。
输入
共一行,包含一个由小写字母构成的字符串S。字符串长度不超过 1000000。
输出
共Length(S)行,每行一个整数,表示答案。
样例输入

aab

样例输出

2
1
1

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
#include <bits/stdc++.h>
const int maxn = 2e6 + 10;
int c[maxn], a[maxn], size[maxn], ans[maxn];
namespace SuffixAutomaton {
int start, last, nodeCnt;
struct node {
int trans[26], next, max, posCnt, min();
}T[maxn];
int node::min() {
return T[next].max + 1;
}
int newnode(int max = 0, bool new_node = true) {
T[++nodeCnt].max = max;
if (new_node)
T[nodeCnt].posCnt = 1;
else
T[nodeCnt].posCnt = 0;
return nodeCnt;
}
void init() {
start = last = newnode();
}
int extend(int c) {
int u = newnode(T[last].max + 1), v = last;
for (; v && !T[v].trans[c]; v = T[v].next) T[v].trans[c] = u;
if (!v) T[u].next = start;
else {
int o = T[v].trans[c];
if (T[o].max == T[v].max + 1) T[u].next = o;
else {
int n = newnode(T[v].max + 1, false);
memcpy(T[n].trans, T[o].trans, sizeof(T[n].trans));
T[n].next = T[o].next; T[o].next = T[u].next = n;
for (; v && T[v].trans[c] == o; v = T[v].next) T[v].trans[c] = n;
}
}return last = u;
}
void calc() {
for(int i = 1; i <= nodeCnt; i++) c[T[i].max]++;
for(int i = 1; i <= nodeCnt; i++) c[i] += c[i - 1];
for(int i = 1; i <= nodeCnt; i++) a[c[T[i].max]--] = i;
for(int i = nodeCnt; i; i--){
int p = a[i], t = T[p].next;
T[t].posCnt += T[p].posCnt;
ans[T[p].max] = std::max(ans[T[p].max], T[p].posCnt);
}
}
}
using namespace SuffixAutomaton;
char s[maxn];
int main() {
init();
scanf("%s", s);
for (int i = 0; s[i]; i++)
extend(s[i] - 'a');
calc();
for (int i = 0; s[i]; i++)
printf("%d\n", ans[i + 1]);
}

模板】后缀自动机

给定一个只包含小写字母的字符串$S$,
请你求出 $S$ 的所有出现次数不为 $1$ 的子串的出现次数乘上该子串长度的最大值。

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
#include <bits/stdc++.h>
const int maxn = 1e6 + 10;
int tax[maxn << 1], rank[maxn << 1];
namespace SuffixAutomaton {
struct node {
int trans[26], next, max, min(), cnt;
}T[maxn << 1];
int node::min() {
return T[next].max + 1;
}
int nodeCnt, start, last;
int newnode(int max = 0, int cnt = 1) {
T[++nodeCnt].max = max; T[nodeCnt].cnt = cnt; return nodeCnt;
}
void init() {
start = last = newnode(0, 0);
}
int extend(int c) {
int u = newnode(T[last].max + 1), v = last;
for (; v && !T[v].trans[c]; v = T[v].next) T[v].trans[c] = u;
if (!v) T[u].next = start;
else {
int o = T[v].trans[c];
if (T[v].max + 1 == T[o].max) T[u].next = o;
else {
int n = newnode(T[v].max + 1, false);
T[n].next = T[o].next; T[o].next = T[u].next = n;
memcpy(T[n].trans, T[o].trans, sizeof(T[o].trans));
for (; v && T[v].trans[c] == o; v = T[v].next) T[v].trans[c] = n;
}
}return last = u;
}
void build(char *s) {
init();
for (int i = 0; s[i]; i++)
extend(s[i] - 'a');
}
int calc() {
long long ans = 0;
for (int i = 1; i <= nodeCnt; i++) ++tax[T[i].max];
for (int i = 1; i <= nodeCnt; i++) tax[i] += tax[i - 1];
for (int i = nodeCnt; i; i--) rank[tax[T[i].max]--] = i;
for (int i = nodeCnt; i; i--) {
int u = rank[i], f = T[u].next;
T[f].cnt += T[u].cnt;
if (T[u].cnt > 1)
ans = std::max(ans, 1ll * T[u].cnt * T[u].max);
}
return ans;
}
}
using namespace SuffixAutomaton;
char str[maxn];
int main() {
scanf("%s", str);
build(str);
printf("%lld\n", calc());
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2018 Anoxiacxy All Rights Reserved.

UV : | PV :