洛谷P3804 【模板】后缀自动机

原题链接:洛谷P3804

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

解法

先建立 SAM,每个子串出现的次数就是对应的 $endpos$ 集合大小。可以考虑按照拓扑序递推优化,或者暴力建树 $\rm DFS$ 求子树大小。

解法一、按拓扑序递推

 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010, M = N * 2;

int n;
char str[N];
struct SAM {
    int maxlen[M], trans[M][26], link[M], sz, last;
    int cnt[M];
    SAM() { sz = last = 1; }
    void init() {
        memset(maxlen, 0, sizeof maxlen);
        memset(trans, 0, sizeof trans);
        memset(link, 0, sizeof link);
        memset(cnt, 0, sizeof cnt);
        sz = last = 1;
    }
    void extend(int ch) {
        int cur = ++sz, p = last;
        maxlen[cur] = maxlen[p] + 1;
        cnt[cur] = 1;
        for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
        if(!p) link[cur] = 1;
        else {
            int q = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
            else {
                int clone = ++sz;
                maxlen[clone] = maxlen[p] + 1;
                memcpy(trans[clone], trans[q], sizeof trans[clone]);
                link[clone] = link[q];
                for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
                link[cur] = link[q] = clone;
            }
        }
        last = cur;
    }
} sam;
LL ans;
int a[M], b[M];

int main() {
    scanf("%s", str);
    for (int i = 0; str[i]; i++) sam.extend(str[i] - 'a');
   	// 基数排序->拓扑序
    for(int i = 1; i <= sam.sz; i++) a[sam.maxlen[i]]++;
    for(int i = 1; i <= sam.sz; i++) a[i] += a[i - 1];
    for(int i = 1; i <= sam.sz; i++) b[a[sam.maxlen[i]]--] = i;
    for(int i = sam.sz; i; i--) {
        int p = b[i];
        sam.cnt[sam.link[p]] += sam.cnt[p];
        if(sam.cnt[p] > 1) ans = max(ans, 1ll * sam.cnt[p] * sam.maxlen[p]);
    }
    cout << ans << endl;
    return 0;
}

解法二、建树DFS每个状态的子树大小

 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010, M = N * 2;

int n;
char str[N];
struct SAM {
    int maxlen[M], trans[M][26], link[M], sz, last;
    int cnt[M];
    SAM() { sz = last = 1; }
    void init() {
        memset(maxlen, 0, sizeof maxlen);
        memset(trans, 0, sizeof trans);
        memset(link, 0, sizeof link);
        memset(cnt, 0, sizeof cnt);
        sz = last = 1;
    }
    void extend(int ch) {
        int cur = ++sz, p = last;
        maxlen[cur] = maxlen[p] + 1;
        cnt[cur] = 1;
        for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
        if(!p) link[cur] = 1;
        else {
            int q = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
            else {
                int clone = ++sz;
                maxlen[clone] = maxlen[p] + 1;
                memcpy(trans[clone], trans[q], sizeof trans[clone]);
                link[clone] = link[q];
                for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
                link[cur] = link[q] = clone;
            }
        }
        last = cur;
    }
} sam;
LL ans;
int h[M], e[M], ne[M], idx;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        sam.cnt[u] += dfs(j);
    }
    if (sam.cnt[u] > 1) ans = max(ans, 1ll * sam.cnt[u] * sam.maxlen[u]);
    return sam.cnt[u];
}

int main() {
    scanf("%s", str);
    for (int i = 0; str[i]; i++) sam.extend(str[i] - 'a');
    // 暴力建树
    memset(h, -1, sizeof h);
    for(int i = 2; i <= sam.sz; i++) add(sam.link[i], i);
    dfs(1);
    cout << ans << endl;
    return 0;
}
updatedupdated2020-05-112020-05-11
加载评论
点击刷新