SPOJ-NSUBSTR - Substrings（SAM求所有长度子串的最大出现次数）

NSUBSTR - Substrings

题面翻译

你得到了一个最多由 $250000$ 个小写拉丁字母组成的字符串 $S$。定义 $F(x)$ 为 $S$ 的某些长度为 $x$ 的子串在 $S$ 中的最大出现次数。即 F(x)=max{times(T)}F(x)=max\{times(T)\}F(x)=max{times(T)}，满足 $T$ 是 $S$ 的子串且 $|T|=x$。例如当 $S=ababa$ 时 $F(3)=2$ ，因为 $S$ 中有一个出现 $2$ 次的子串 $aba$。 你的任务是对于每个 $1\le i\le |S|$ 输出 $F(i)$。

题目描述

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

3
2
2
1
1

题意：

给一个字符串S，令F(x)表示S的所有长度为x的子串中，出现次数的最大值。求F(1)…F(Length(S))

思路：

构建 s 的 SAM，对于每个 SAM 状态 u 能表示的子串长度范围是 [ len[fa(u)] + 1, len[s] ]，这些子串的出现次数等价于 cnt[u]。

那么问题变成用 cnt[u] 去区间更新 [ len[fa(u)] + 1, len[u] ] 的最大值。（无脑线段树？SPOJ 时限仅 100 ms，喜提TLE。怎么优化呢？）

我们发现 f[i] 是非严格单调递减的，我们 只用 cnt[u] 去更新 f[len[u]]， 然后使用推标记的方法，从后向前令 f[i] = max(f[i], f[i + 1]) 即可。

代码：

#include<bits/stdc++.h>using namespace std;const int N = 2.5e5 + 10, M = N << 1;
int ch[M][26], len[M], fa[M], np = 1, tot = 1;
long long cnt[M], f[N];
vector<int> g[M];
char s[N];void extend(int c)
{int p = np; np = ++tot;len[np] = len[p] + 1, cnt[np] = 1;while (p && !ch[p][c]) {ch[p][c] = np;p = fa[p];}if (!p) {fa[np] = 1;}else {int q = ch[p][c];if (len[q] == len[p] + 1) {fa[np] = q;}else {int nq = ++tot;len[nq] = len[p] + 1;fa[nq] = fa[q], fa[q] = fa[np] = nq;while (p && ch[p][c] == q) {ch[p][c] = nq;p = fa[p];}memcpy(ch[nq], ch[q], sizeof ch[q]);}}
}void dfs(int u)
{for (auto son : g[u]) {dfs(son);cnt[u] += cnt[son];}int l = len[fa[u]] + 1, r = len[u];f[r] = max(1ll * f[r], 1ll * cnt[u]);
}signed main()
{scanf("%s", s);int n = strlen(s);for (int i = 0; s[i]; ++i) {extend(s[i] - 'a');}for (int i = 2; i <= tot; ++i) {g[fa[i]].emplace_back(i);}dfs(1);for (int i = n - 1; i >= 1; --i) {f[i] = max(f[i], f[i + 1]);}for (int i = 1; i <= n; ++i) {printf("%lld\n", f[i]);}return 0;
}