首页 > 代码库 > [SPOJ8222]Substrings
[SPOJ8222]Substrings
[SPOJ8222]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).
输入示例
ababa
输出示例
3 2 2 1 1
数据规模及约定
见“输入”
题解
构造后缀自动机,然后用每个节点 i 的 righti 集合大小更新 f[Max[i]],然后再用每个 f[i] 更新 f[i-1]。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std; int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } #define maxn 500010 #define maxa 26 int n; int ToT, rt, last, ch[maxn][maxa], par[maxn], Max[maxn], siz[maxn]; void extend(int x) { int p = last, np = ++ToT; Max[np] = Max[p] + 1; siz[np] = 1; last = np; while(p && !ch[p][x]) ch[p][x] = np, p = par[p]; if(!p){ par[np] = rt; return ; } int q = ch[p][x]; if(Max[q] == Max[p] + 1){ par[np] = q; return ; } int nq = ++ToT; Max[nq] = Max[p] + 1; memcpy(ch[nq], ch[q], sizeof(ch[q])); par[nq] = par[q]; par[q] = nq; par[np] = nq; while(p && ch[p][x] == q) ch[p][x] = nq, p = par[p]; return ; } int f[maxn]; char Str[maxn]; int sa[maxn], Ws[maxn]; void build() { for(int i = 1; i <= ToT; i++) Ws[n-Max[i]]++; for(int i = 1; i <= n; i++) Ws[i] += Ws[i-1]; for(int i = ToT; i; i--) sa[Ws[n-Max[i]]--] = i; for(int i = 1; i <= ToT; i++) siz[par[sa[i]]] += siz[sa[i]]; return ; } int main() { scanf("%s", Str); n = strlen(Str); rt = last = ToT = 1; for(int i = 0; i < n; i++) extend(Str[i] - ‘a‘); build(); for(int i = 1; i <= ToT; i++) f[Max[i]] = max(f[Max[i]], siz[i]); for(int i = n; i > 1; i--) f[i-1] = max(f[i], f[i-1]); for(int i = 1; i <= n; i++) printf("%d\n", f[i]); return 0; }
[SPOJ8222]Substrings
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。