Blackops

初心易得，始终难守

0%

SPOJ NSUBSTR Substrings（后缀自动机+parent树）

发表于 分类于 ， ，

NSUBSTR - Substrings
suffix-array-8

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|.
Input

String S consists of at most 250000 lowercase latin letters.

Output

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

Example

Input:
ababa

Output:
3
2
2
1
1

题目链接：SPOJ NSUBSTR
题意就是输出长度为$i$的子串最多出现的次数（可重复），由于每一个节点$L[i]$都是一个子串，那么根据$parent$树的性质，先把$endpos$设为1，然后从下往上叠加上去，然后遍历所有节点，$L[i].len$就是当前节点作为接受态形成子串的长度，那么只要$ans[L[i].len] = max(ans[L[i].len], L[i].endpos)$就可以了
不知道为什么最后一定要从后往前更新一遍，不更新也可以过数据啊，反正先这么写了吧
代码：

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 250010;
struct Trie
{
    int nxt[26], pre, len, v;
    void init()
    {
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
        pre = -1;
        v = 0;
    }
} L[N << 1];
int sz, last;
char s[N];
int cnt[N], x[N << 1];
int ans[N];

inline void init()
{
    sz = last = 0;
    L[sz++].init();
    CLR(cnt, 0);
    CLR(ans, 0);
}
inline int newnode()
{
    L[sz].init();
    return sz++;
}
void ins(int c)
{
    int u = newnode();
    L[u].len = L[last].len + 1;
    L[u].v = 1;
    int t = last;
    while (t != -1 && L[t].nxt[c] == -1)
    {
        L[t].nxt[c] = u;
        t = L[t].pre;
    }
    if (t == -1)
        L[u].pre = 0;
    else
    {
        int v = L[t].nxt[c];
        if (L[t].len + 1 == L[v].len)
            L[u].pre = v;
        else
        {
            int np = newnode();
            L[np] = L[v];
            L[np].len = L[t].len + 1;
            L[np].v = 0;
            L[np].pre = L[v].pre;
            L[u].pre = L[v].pre = np;
            while (t != -1 && L[t].nxt[c] == v)
            {
                L[t].nxt[c] = np;
                t = L[t].pre;
            }
        }
    }
    last = u;
}
int main(void)
{
    int i;
    while (~scanf("%s", s))
    {
        init();
        int len = strlen(s);
        for (i = 0; i < len; ++i)
            ins(s[i] - 'a');
        for (i = 0; i < sz; ++i)
            ++cnt[L[i].len];
        for (i = 1; i <= len; ++i)
            cnt[i] += cnt[i - 1];
        for (i = sz - 1; i >= 0; --i)
            x[--cnt[L[i].len]] = i;
        for (i = sz - 1; i >= 1; --i)
            L[L[x[i]].pre].v += L[x[i]].v;
        for (i = 0; i < sz; ++i)
            ans[L[i].len] = max(ans[L[i].len], L[i].v);
        for (i = len; i >= 1; --i)//这里感觉不必要啊？？
            ans[i] = max(ans[i], ans[i + 1]);
        for (i = 1; i <= len; ++i)
            printf("%d\n", ans[i]);
    }
    return 0;
}