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|.
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
题意：
有字符串$S$，$|S|\leq 250000$。我们将 $F(x)$定义为某些长度$x$的字符串在$S$中出现的最大次数。例如字符串==ababaf==，因为有一个字符串==aba==出现两次。你的任务是输出$F(x)$每一个$x$，以使$1<=x<=|S|$。
题解：
因为对于S的任意子串，都是由初始状态出发走到某个状态u得到的（子串对应的状态唯一）。而SAM中的endpos标记了该子串出现的所有位置，因此为了获得所有子串的数量，我们首先要求出endpos集合的大小，采用记忆化搜索。
定义：
EndPosSize[u]为状态u的endpos的大小。
初始化：
每添加一个字符，当前的状态的EndPos=1。其他的为0。
即当前状态至少存在一个endpos，就是当前添加的位置。
转移方程：
因为在后缀连接树中，子节点是对父节点的一种不重复的划分，因此父节点的endpos大小就是其所有子节点endpos大小的和。
这样我们就求出了每个状态的endpos的大小。而根据后缀连接树的性质，每个状态的字符串集合种的字符串都是连续的，且长度区间为$[len(link(u))+1…len(u)]$，其中u为当前状态。
至此，endpos为每个状态的大小，又有了每个状态的对应的长度，直接更新取最大即可。当由于后缀连接树很可能不是平衡的，因此区间更新所有状态的时间复杂度为$O(|S|^2)$，会超时。可以采用线段树优化区间更新，时间复杂度为$O(|S|log|S|)$。
AC代码：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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
using namespace std;
const int MAXN = 250005;
int n;
int EndPosSize[2 * MAXN];
char S[MAXN];
//后缀自动机
struct SAM {
int size, last;
struct Node {
int len, link;
int next[26];
void clear() {
len = link = 0;
memset(next, 0, sizeof(next));
}
} node[MAXN * 2];
void init() {
for (int i = 0; i < size; i++) {
node[i].clear();
}
node[0].link = -1;
size = 1;
last = 0;
}
void insert(char x) {
int ch = x - 'a';
int cur = size++;
EndPosSize[cur] = 1;
node[cur].len = node[last].len + 1;
int p = last;
while (p != -1 && !node[p].next[ch]) {
node[p].next[ch] = cur;
p = node[p].link;
}
if (p == -1) {
node[cur].link = 0;
}
else {
int q = node[p].next[ch];
if (node[p].len + 1 == node[q].len) {
node[cur].link = q;
}
else {
int clone = size++;
node[clone] = node[q];
node[clone].len = node[p].len + 1;
while (p != -1 && node[p].next[ch] == q) {
node[p].next[ch] = clone;
p = node[p].link;
}
node[q].link = node[cur].link = clone;
}
}
last = cur;
}
}sam;
//后缀连接树建图
vector<int> G[2 * MAXN];
//保存F（x）
int Ans[MAXN];
//记忆化搜索
int DFS(int Cur) {
//加上所有子节点
for (int i = 0; i < G[Cur].size(); ++i) {
int& Next = G[Cur][i];
EndPosSize[Cur] += DFS(Next);
}
return EndPosSize[Cur];
}
//线段树
class SegmentTree{
int
Data[MAXN * 4],
LazyTag[MAXN * 4];
public:
void PushUp(const int& root) {
this->Data[root] = this->Data[root << 1] + this->Data[root << 1 | 1];
}
void PushDown(int root, int len) {
if (!this->LazyTag[root]) {
return;
}
const int
&& LeftSon = root << 1,
&& RightSon = root << 1 | 1;
this->LazyTag[LeftSon] = max(this->LazyTag[LeftSon], this->LazyTag[root]);
this->LazyTag[RightSon] = max(this->LazyTag[RightSon], this->LazyTag[root]);
this->Data[LeftSon] = max(this->Data[LeftSon], this->LazyTag[root]);
this->Data[RightSon] = max(this->Data[RightSon], this->LazyTag[root]);
this->LazyTag[root] = 0;
}
void UpGrade(const int& left, const int& right, int leftcur, int rightcur, int root,const int& val) {
if (leftcur >= left && rightcur <= right) {
this->Data[root] = max(this->Data[root], val);
this->LazyTag[root] = max(this->LazyTag[root], val);
return;
}
this->PushDown(root, rightcur - leftcur + 1);
const int&& mid = (leftcur + rightcur) >> 1;
if (mid >= left) {
this->UpGrade(left, right, leftcur, mid, root << 1, val);
}
if (mid + 1 <= right) {
this->UpGrade(left, right, mid + 1, rightcur, root << 1 | 1, val);
}
this->PushUp(root);
}
int Query(const int& left, const int& right, int leftcur, int rightcur, int root) {
if (leftcur >= left && rightcur <= right) {
return this->Data[root];
}
int&& Ans = 0;
const int&& mid = (leftcur + rightcur) >> 1;
this->PushDown(root, rightcur - leftcur + 1);
if (mid >= left) {
Ans += this->Query(left, right, leftcur, mid, root << 1);
}
if (mid + 1 <= right) {
Ans += this->Query(left, right, mid + 1, rightcur, root << 1 | 1);
}
return Ans;
}
}Tree;
int main() {
scanf("%s", S);
int&& n = strlen(S);
sam.init();
for (int i = 0; i < n; ++i) {
sam.insert(S[i]);
}
//建树
for (int i = 1; i < sam.size; ++i) {
if (sam.node[i].link != -1) {
G[sam.node[i].link].push_back(i);
}
}
//求EndPosSize
DFS(0);
//答案更新
for (int i = 1; i < sam.size; ++i) {
int&& Left = sam.node[sam.node[i].link].len + 1;
Left = max(1, Left);
Tree.UpGrade(Left, sam.node[i].len, 1, n, 1, EndPosSize[i]);
}
for (int i = 1; i <= n; ++i) {
printf("%d\n", Tree.Query(i, i, 1, n, 1));
}
return 0;
}
