就是后缀自动机的板子嘛.. 构造完自动机之后拓扑一下, 记录 size, 对于 size 大于 k 的点和 ans 取 max
- #include
- #include
- #include
- #include
- using namespace std;
- const int N=100005;
- int n,m,a[N],cur=1,cnt=1;
- int read()
- {
- int r=0,f=1;
- char p=getchar();
- while(p>'9'||p<'0')
- {
- if(p=='-')
- f=-1;
- p=getchar();
- }
- while(p>='0'&&p<='9')
- {
- r=r*10+p-48;
- p=getchar();
- }
- return r*f;
- }
- struct SAM
- {
- int la,fa[N],len[N],si[N],sa[N],c[N],ans;
- map<int,int>ch[N];
- void ins(int c,int id)
- {
- la=cur;
- cur=++cnt;
- len[cur]=id;
- int p=la;
- for(;p&&!ch[p][c];p=fa[p])
- ch[p][c]=cur;
- if(!p)
- fa[cur]=1;
- else
- {
- int q=ch[p][c];
- if(len[q]==len[p]+1)
- fa[cur]=q;
- else
- {
- int nt=++cnt;
- len[nt]=len[p]+1;
- ch[nt]=ch[q];
- fa[nt]=fa[q];
- fa[cur]=fa[q]=nt;
- for(;p&&ch[p][c]==q;p=fa[p])
- ch[p][c]=nt;
- }
- }
- si[cur]=1;
- }
- void wk()
- {
- for(int i=1;i<=cnt;i++)
- c[len[i]]++;
- for(int i=1;i<=n;i++)
- c[i]+=c[i-1];
- for(int i=cnt;i>=1;i--)
- sa[c[len[i]]--]=i;
- for(int i=cnt;i>=1;i--)
- {
- if(si[sa[i]]>=m&&ans<len[sa[i]])
- ans=len[sa[i]];
- si[fa[sa[i]]]+=si[sa[i]];
- }
- }
- }sam;
- int main()
- {
- n=read(),m=read();
- for(int i=1;i<=n;i++)
- a[i]=read(),sam.ins(a[i],i);
- sam.wk();
- printf("%d\n",sam.ans);
- return 0;
- }
暗搓搓留念
来源: http://www.bubuko.com/infodetail-2574552.html