目录

SP8222-NSUBSTR - Substrings

2021-01-01 约 523 字预计阅读 2 分钟次阅读

目录

SP8222-NSUBSTR - Substrings

题目:

题目描述:

You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string ‘ababa’ F(3) will be 2 because there is a string ‘aba’ that occurs twice. Your task is to output F(i) for every i so that 1<=i<=|S|.

输入格式:

String S consists of at most 250000 lowercase latin letters.

输出格式:

Output |S| lines. On the i-th line output F(i).

样例:

样例输入1:

1
ababa

样例输出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
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
// Problem: SP8222 NSUBSTR - Substrings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP8222
// Memory Limit: 1.46 MB
// Time Limit: 149 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
int n, nl;
const int maxn = 3 * 1e6 + 100;
char s[maxn];
int ans[maxn];
struct sam
{
    int mp[maxn][26];
    struct edge
    {
        int nxt, v;
    } e[maxn];
    int tot, cnt, las, len[maxn], head[maxn], siz[maxn], fa[maxn];
    void add(int u, int v)
    {
        e[++tot].v = v;
        e[tot].nxt = head[u];
        head[u] = tot;
    }
    void ins(int c)
    {
        int p = las;
        siz[las = ++cnt] = 1;
        len[las] = nl;
        for (; p && mp[p][c] == 0; p = fa[p])
        {
            mp[p][c] = las;
        }
        if (p == 0)
        {
            fa[las] = 1;
            return;
        }
        int q = mp[p][c];
        if (len[p] + 1 == len[q])
        {
            fa[las] = q;
            return;
        }
        len[++cnt] = len[p] + 1;
        for (int i = 0; i < 26; i++)
        {
            mp[cnt][i] = mp[q][i];
        }
        fa[cnt] = fa[q];
        fa[q] = cnt;
        fa[las] = cnt;
        for (int i = p; mp[i][c] == q; i = fa[i])
        {
            mp[i][c] = cnt;
        }
    }
    inline void jt()
    {
        for (int i = 2; i <= cnt; i++)
        {
            add(fa[i], i);
        }
    }
    void dfs(int u)
    {
        for (int i = head[u]; i; i = e[i].nxt)
        {
            dfs(e[i].v);
            siz[u] += siz[e[i].v];
        }
        // if (siz[u] != 1)
        {
            ans[len[u]] = max(ans[len[u]], siz[u]);
        }
    }
} sam;
int main()
{
    cerr << "!!!" << endl;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    sam.cnt = sam.las = 1;
    for (nl = 1; nl <= n; nl++)
        sam.ins(s[nl] - 'a');
    sam.jt();
    sam.dfs(1);
    for (int i = 1; i <= n; i++)
        yout << ans[i] << endl;
    return 0;
}