spoj8222
2024-09-21 23:23:11
地址:
题目:
NSUBSTR - Substrings
no tags
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
思路:
先求出每个状态的endpos集合大小,用cnt记录,用cnt[s]去更新f[len[s]],再用f[i+1]去更新f[i].
#include <bits/stdc++.h> using namespace std; char ss[];
int ans,f[<<]; struct SAM
{
static const int MAXN = <<;//大小为字符串长度两倍
static const int LetterSize = ; int tot, last, ch[MAXN][LetterSize], fa[MAXN], len[MAXN];
int sum[MAXN], tp[MAXN], cnt[MAXN]; //sum,tp用于拓扑排序,tp为排序后的数组 void init( void)
{
last = tot = ;
len[] = ;
memset(ch,,sizeof ch);
memset(fa,,sizeof fa);
memset(cnt,,sizeof cnt);
} void add( int x)
{
int p = last, np = last = ++tot;
len[np] = len[p] + , cnt[last] = ;
while( p && !ch[p][x]) ch[p][x] = np, p = fa[p];
if( p == )
fa[np] = ;
else
{
int q = ch[p][x];
if( len[q] == len[p] + )
fa[np] = q;
else
{
int nq = ++tot;
memcpy( ch[nq], ch[q], sizeof ch[q]);
len[nq] = len[p] + , fa[nq] = fa[q], fa[q] = fa[np] = nq;
while( p && ch[p][x] == q) ch[p][x] = nq, p = fa[p];
}
}
} void toposort( void)
{
for(int i = ; i <= len[last]; i++) sum[i] = ;
for(int i = ; i <= tot; i++) sum[len[i]]++;
for(int i = ; i <= len[last]; i++) sum[i] += sum[i-];
for(int i = ; i <= tot; i++) tp[sum[len[i]]--] = i;
for(int i = tot; i; i--) cnt[fa[tp[i]]] += cnt[tp[i]];
}
} sam; int main(void)
{
//freopen("in.acm","r",stdin);
sam.init();
scanf("%s",ss);
for(int i=,len=strlen(ss);i<len;i++) sam.add(ss[i]-'a');
sam.toposort();
for(int i=;i<=sam.tot;i++) f[sam.len[i]]=max(f[sam.len[i]],sam.cnt[i]);
for(int i=sam.len[sam.last];i;i--) f[i]=max(f[i],f[i+]);
for(int i=;i<=sam.len[sam.last];i++) printf("%d\n",f[i]);
return ;
}
最新文章
- UVA 11384 正序数排列
- 原生Ajax写法(GET)
- NodeJS的安装
- c语言 typedef
- 带有&#215;的EditText
- JSON 之FastJson解析
- Mustache学习
- JAVA 线程学习 - Thread了解
- [LeetCode]题解(python):009-Palindrome Number
- HDU 2243 Knight Moves
- 安装MySQL后出现发生系统错误2或者系统找不到指定的文件
- Mahout 算法
- Eclipse 3.5 以后安装插件很慢的解决办法
- ddt运行测试方法时报错AttributeError: type object &#39;TestHttpRq&#39; has no attribute &#39;test_http_rq_login&#39;
- js一些格式化
- webRTC中音频相关的netEQ(二):数据结构
- Windows 快捷方式(*.link)打开方式关联错误
- JS判断手机端是否安装某应用
- Photobucket不能用了怎么办?推荐10个在线图片储存服务!
- Confluence 6 管理多目录