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
spoj又回归正常了╮(╯▽╰)╭~ 然而咱的智商并没有(╯‵□′)╯︵┻━┻ sizeof()打错咱还是头一回…… 大触们在发明新方法，而蒟蒻却在发明新错法……
思路: right数组…… 喂这玩意为什么咱以前没有听说过啊啊啊！！！(╯‵□′)╯︵┻━┻ 就当是学习了一些人生经验新知识吧~
right数组意义:节点代表的所有的子串的右端点在原串中的位置构成的集合。 那么这个绕口的玩意有什么用呢？ 当然有用了，这题的答案就是它的元素个数……
先初始化原串在自动机上跑一边所经过的每一个节点right大小为1。 然后按拓扑序对每个节点传递大小至其父亲，就能求出所有right的大小。 然后用DP跑一边，这题做完了~
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int N=501233; struct SAM { int next[N][26],fa[N],len[N]; int pool,u; inline void init() { pool=u=1; } inline void add(int v) { int now=++pool; len[now]=len[u]+1; while(!next[u][v] && u) next[u][v]=now,u=fa[u]; if(!u) fa[now]=1; else { int q=next[u][v]; if(len[q]==len[u]+1) fa[now]=q; else { int newq=++pool; memcpy(next[newq],next[q],sizeof(next[q]));//打成sizeof(q)的本蒟蒻智商堪忧...... fa[newq]=fa[q]; len[newq]=len[u]+1; fa[q]=fa[now]=newq; while(next[u][v]==q) next[u][v]=newq,u=fa[u]; } } u=now; } }koishi; int sum[N],id[N],r[N]; int f[N]; int main() { koishi.init(); char s[N]; scanf("%s",s+1); int len=strlen(s+1); for(int i=1;i<=len;++i) koishi.add(s[i]-'a'); int p=1; for(int i=1;i<=len;++i) p=koishi.next[p][s[i]-'a'],++r[p]; for(int i=1;i<=koishi.pool;++i) ++sum[koishi.len[i]]; for(int i=1;i<=len;++i) sum[i]+=sum[i-1]; for(int i=1;i<=koishi.pool;++i) id[sum[koishi.len[i]]--]=i; for(int i=koishi.pool;i;--i) r[koishi.fa[id[i]]]+=r[id[i]]; for(int i=1;i<=koishi.pool;i++) f[koishi.len[i]]=max(f[koishi.len[i]],r[i]); for(int i=len;i;i--) f[i]=max(f[i+1],f[i]); for(int i=1;i<=len;i++) printf("%d\n",f[i]); return 0; }