#1449 : 后缀自动机三·重复旋律6
时间限制:15000ms
单点时限:3000ms
内存限制:512MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。
现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的，小Hi想知道对于所有的K的答案。
输入
共一行，包含一个由小写字母构成的字符串S。字符串长度不超过 1000000。
输出
共Length(S)行，每行一个整数，表示答案。
- 样例输入
-
aab
- 样例输出
-
2
1
1
- 要求长度为k的子串中出现次数最多的串的出现次数
- 对于每个节点代表的子串出现次数的求法是拓扑排序之后从len最大的逐步向前更新之前节点的出现次数
- 原理是沿着par指针向前访问节点意味着访问的是同一最大子串的连续的子串
- 比如长度最大的串是abcdef是len最大的节点表示的最长串，最短串是abcd，那么沿par指针访问前一个节点，那么前一个节点表示的子串是ab到abc，所以最长串出现多少次，沿par访问的串就会出现多少次
- 在实际操作过程中对于extend操作中第一个新建的节点，打标记，意思当前串出现1次，而extend操作中衍生出的nq节点就标记为0
- 自动机完成后就是对于自动机拓扑排序，用len长的更新len短的得到每一个节点代表子串出现次数，用ans[length]记录每个长度的最大出现次数
- 但是要注意此时的ans数组不是最后答案，因为ans数组还要满足一个基本条件，即段子串出现次数一定比长子串出现次数多，就是说ans数组应该是一个非严格递减序列
- 我们倒着遍历ans数组，ans[i]=max(ans[i],ans[i+1]);
- 原因也好总结，因为后缀数组记录的len是匹配最大长度，我们没有记录minlen，所以对于一个节点出现次数我们没有更新对应的minlen对应长度的出现次数，就是说在不同自动机路径中我们没法保证把1到n长度子串出现次数全部一次性统计正确，因为会有路径上将很多长度的子串次数集中记录在最大的长度len上而没有对于小长度进行更新
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long LL ;
typedef unsigned long long ULL ;
const int maxn = 1e6 + ;
const int inf = 0x3f3f3f3f ;
const int npos = - ;
const int mod = 1e9 + ;
const int mxx = + ;
const double eps = 1e- ;
const double PI = acos(-1.0) ; struct cnode{
int len, st;
cnode(int x, int y){
len=x; st=y;
}
};
bool ccmp(const cnode l, const cnode r){
return l.len>r.len;
}
struct SAM{
int n, tot, root, last;
int cnt[maxn<<], ans[maxn];
struct node{
int len, flag;
int link, go[];
};
node state[maxn<<];
void init(char *str){
n=strlen(str);
tot=;
root=;
last=;
memset(&state,,sizeof(state));
}
void extend(int w){
tot++;
int p=last;
int np=tot;
state[np].len=state[p].len+;
state[np].flag=;
while(p && state[p].go[w]==){
state[p].go[w]=np;
p=state[p].link;
}
if(p==){
state[np].link=root;
}else{
int q=state[p].go[w];
if(state[p].len+==state[q].len){
state[np].link=q;
}else{
tot++;
int nq=tot;
state[nq].len=state[p].len+;
state[nq].flag=;
memcpy(state[nq].go,state[q].go,sizeof(state[q].go));
state[nq].link=state[q].link;
state[q].link=nq;
state[np].link=nq;
while(p && state[p].go[w]==q){
state[p].go[w]=nq;
p=state[p].link;
}
}
}
last=np;
}
void build(char *str){
init(str);
for(int i=;i<n;i++)
extend(str[i]-'a');
}
std::vector<cnode> v;
void solve(void){
v.clear();
for(int i=;i<=tot;i++){
cnt[i]=state[i].flag;
v.push_back(cnode(state[i].len,i));
}
sort(v.begin(),v.end(),ccmp);
for(int i=;i<v.size();i++){
cnt[state[v[i].st].link]+=cnt[v[i].st];
}
memset(ans,,sizeof(ans));
for(int i=;i<=tot;i++)
ans[state[i].len]=max(ans[state[i].len],cnt[i]);
for(int i=n-;i>;i--)
ans[i]=max(ans[i],ans[i+]);
for(int i=;i<=n;i++)
printf("%d\n",ans[i]);
}
};
SAM A;
char str[maxn];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(~scanf("%s",str)){
A.build(str);
A.solve();
}
return ;
}