SPOJ8222 NSUBSTR - Substrings(后缀自动机)
2018-06-29 06:14:37来源:博客园 阅读 ()
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
为什么我的后缀自动机写的这么奇怪qwq。。
为什么泥萌都在写桶排??!!
这题不是dfs一下求出$right$集合来就完了么qwq、、
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN = 250001 << 1, INF = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } char s[MAXN]; int N; int f[MAXN], siz[MAXN], fa[MAXN], len[MAXN], ch[MAXN][26], root = 1, last = 1, tot = 1; void insert(int x) { int now = ++tot, pre = last; last = now; siz[now] = 1; len[now] = len[pre] + 1; for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now; if(!pre) fa[now] = root; else { int q = ch[pre][x]; if(len[q] == len[pre] + 1) fa[now] = q; else { int nows = ++tot; memcpy(ch[nows], ch[q], sizeof(ch[q])); fa[nows] = fa[q]; fa[q] = fa[now] = nows; len[nows] = len[pre] + 1; for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nows; } } } vector<int> v[MAXN]; void dfs(int x) { for(int i = 0; i < v[x].size(); i++) { dfs(v[x][i]); siz[x] += siz[v[x][i]]; } f[len[x]] = max(f[len[x]], siz[x]); } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #else //freopen("pow.in", "r", stdin); //freopen("pow.out", "w", stdout); #endif scanf("%s", s + 1); N = strlen(s + 1); for(int i = 1; i <= N; i++) insert(s[i] - 'a'); for(int i = 2; i <= tot; i++) v[fa[i]].push_back(i); dfs(root); for(int i = 1; i <= N; i++) printf("%d\n", f[i]); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash