首页 > 代码库 > SPOJ 8222 Substrings（后缀自动机）
SPOJ 8222 Substrings（后缀自动机）
【题目链接】 http://www.spoj.com/problems/NSUBSTR/
【题目大意】
给一个字符串S，令F(x)表示S的所有长度为x的子串中，出现次数的最大值。
求出所有的F。
【题解】
在SAM中，一个串出现的次数就是|Right(s)|，我们按长度从小到大分配内存单位，
从后往前计算可以获得Right值大小，用所有的Right去更新相应长度的答案即可。
【代码】
#include <cstdio>#include <cstring>#include <algorithm> using namespace std;const int N=500005;char s[N];struct sam{ int p,q,np,nq,cnt,last,a[N][26],l[N],f[N]; sam(){cnt=0;last=++cnt;} void extend(int c){ p=last;np=last=++cnt;l[np]=l[p]+1; while(!a[p][c]&&p)a[p][c]=np,p=f[p]; if(!p)f[np]=1; else{ q=a[p][c]; if(l[p]+1==l[q])f[np]=q; else{ nq=++cnt;l[nq]=l[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); f[nq]=f[q]; f[np]=f[q]=nq; while(a[p][c]==q)a[p][c]=nq,p=f[p]; } } }int b[N],x[N],r[N]; void build(){ scanf("%s",s+1); int len=strlen(s+1); for(int i=1;i<=len;i++)extend(s[i]-‘a‘); for(int i=1;i<=cnt;i++)b[l[i]]++; for(int i=1;i<=len;i++)b[i]+=b[i-1]; for(int i=1;i<=cnt;i++)x[b[l[i]]--]=i; for(int i=p=1;i<=len;i++){p=a[p][s[i]-‘a‘];r[p]++;} for(int i=cnt;i;i--)r[f[x[i]]]+=r[x[i]]; } int F[N]; void CalF(){ int len=strlen(s+1); for(int i=1;i<=cnt;i++)F[l[i]]=max(F[l[i]],r[i]); for(int i=1;i<=len;i++)printf("%d\n",F[i]); }}sam;int main(){ sam.build(); sam.CalF(); return 0;}
SPOJ 8222 Substrings（后缀自动机）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。