网站建设的核心是什么,湖南省建设厅网站首页,东西湖区网站建设公司,火车头wordpress 4.7NSUBSTR - Substrings
题面翻译
你得到了一个最多由 250000250000250000 个小写拉丁字母组成的字符串 SSS。定义 F(x)F(x)F(x) 为 SSS 的某些长度为 xxx 的子串在 SSS 中的最大出现次数。即 F(x)max{times(T)}F(x)max\{times(T)\}F(x)max{times(T)}#xff0c;满足 TTT 是 S…NSUBSTR - Substrings
题面翻译
你得到了一个最多由 250000250000250000 个小写拉丁字母组成的字符串 SSS。定义 F(x)F(x)F(x) 为 SSS 的某些长度为 xxx 的子串在 SSS 中的最大出现次数。即 F(x)max{times(T)}F(x)max\{times(T)\}F(x)max{times(T)}满足 TTT 是 SSS 的子串且 ∣T∣x|T|x∣T∣x。例如当 SababaSababaSababa 时 F(3)2F(3)2F(3)2 因为 SSS 中有一个出现 222 次的子串 abaabaaba。 你的任务是对于每个 1≤i≤∣S∣1\le i \le |S|1≤i≤∣S∣ 输出 F(i)F(i)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 1i|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]) 即可。
代码
#includebits/stdc.husing 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];
vectorint 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;
}
