本文共 2064 字，大约阅读时间需要 6 分钟。
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。
现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的，小Hi想知道对于所有的K的答案。
共一行，包含一个由小写字母构成的字符串S。字符串长度不超过 1000000。
共Length(S)行，每行一个整数，表示答案。
aab
211
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;const int inf=0x3f3f3f3f;const int N=1e6+100;const int M=1e6+5;int tot,slink[2*N],trans[2*N][26],minlen[2*N],maxlen[2*N],edpts[2*N];char str[2*N];int n;int containPrefix[2*N],ind[2*N],ans[2*N+10];int newstate(int _maxlen,int _minlen,int* _trans,int _slink) { maxlen[++tot]=_maxlen; minlen[tot]=_minlen; slink[tot]=_slink; if(_trans) for(int i=0; i<26; i++) trans[tot][i]=_trans[i]; return tot;}int add_char(char ch,int u) { int c=ch-'a',v=u; int z=newstate(maxlen[u]+1,-1,NULL,0); containPrefix[z]=1; while(v&&!trans[v][c]) { trans[v][c]=z; v=slink[v]; } if(!v) { minlen[z]=1; slink[z]=1; ind[0]++; return z; } int x=trans[v][c]; if(maxlen[v]+1==maxlen[x]) { slink[z]=x; minlen[z]=maxlen[x]+1; ind[x]++; return z; } int y=newstate(maxlen[v]+1,-1,trans[x],slink[x]); slink[z]=slink[x]=y; ind[y]+=2; minlen[x]=minlen[z]=maxlen[y]+1; while(v&&trans[v][c]==x) { trans[v][c]=y; v=slink[v]; } minlen[y]=maxlen[slink[y]]+1; return z;}void getEndPtCount() { queue q; for( int i=1; i <=tot; i++ )if( !ind[i] ) { q.push(i); //edpts[i] = maxlen[i]-minlen[i]; // +1; programming convenient purpose } while( !q.empty() ) { int u = q.front(); q.pop(); if( containPrefix[u] ) edpts[u]++; edpts[ slink[u]] += edpts[u]; if( !--ind[slink[u]] ) q.push(slink[u]); }}int main() { scanf("%s",str); int len=strlen(str),pre=1; tot=1; for(int i=0; i 0;i--){ mm=ans[i]=max(ans[i],mm); } for(int i=1;i<=len;i++)printf("%d\n",ans[i]); return 0;}
转载于:https://www.cnblogs.com/jianrenfang/p/6344820.html