http://hihocoder.com/problemset/problem/1449
求长度为k的子串出现次数最多的是多少
求完sam后,直接topo,然后更新所有长度即可
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod (1000000007) #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=2000000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; char s[N],p[N]; int sz[N],c[N],a[N],ans[N]; struct SAM{ int last,cnt; int ch[N<<1][26],fa[N<<1],l[N<<1]; void ins(int c){ int p=last,np=++cnt;last=np;l[np]=l[p]+1; for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(l[p]+1==l[q])fa[np]=q; else{ int nq=++cnt;l[nq]=l[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); fa[nq]=fa[q];fa[q]=fa[np]=nq; for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq; } } sz[np]=1; } void build(){ scanf("%s",s+1); int len=strlen(s+1); last=cnt=1; for(int i=1;i<=len;i++)ins(s[i]-'a'); topo(); } void topo(){ for(int i=1;i<=cnt;i++)c[l[i]]++; for(int i=1;i<=cnt;i++)c[i]+=c[i-1]; for(int i=1;i<=cnt;i++)a[c[l[i]]--]=i; } void cal() { for(int i=cnt;i;i--) { int p=a[i]; sz[fa[p]]+=sz[p]; ans[l[p]]=max(ans[l[p]],sz[p]); } int len=strlen(s+1); for(int i=1;i<=len;i++) printf("%d ",ans[i]); } }sam; int main() { sam.build(); sam.cal(); return 0; } /******************** ********************/