题目描述

输入输出格式

输入格式：

 

 

输出格式：

 

 

输入输出样例

输入样例#1： 

3baaaababababbababbab11baaaababababbababbab3cccccc0

输出样例#1： 

5 12none4 2     这个题后缀数组或者二分+hash好像都能做，，，但是我只是练一下后缀自动机而已hhhhh 这个题我们求的显然就是right集合大小>=m的max{}的最大值，至于求最右开端的话，我们只需要记录一下 right集合的最右点是哪个就行了，然后用这个减去答案长度就是最右开端。

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long long#define maxn 170005using namespace std;int l[maxn],siz[maxn],n,r[maxn];int cnt=1,pre=1,m,ans,pos;int ch[maxn][26],f[maxn];int a[maxn],c[maxn];char s[maxn];inline void init(){ memset(ch,0,sizeof(ch)); memset(f,0,sizeof(f)); memset(c,0,sizeof(c)); memset(siz,0,sizeof(siz)); memset(r,0,sizeof(r)); cnt=pre=1,l[1]=siz[1]=0; ans=pos=0;}inline void ins(int x){ int p=pre,np=++cnt; pre=np,l[np]=l[p]+1; siz[np]=1,r[np]=l[np]; for(;p&&!ch[p][x];p=f[p]) ch[p][x]=np; if(!p) f[np]=1; else{ int q=ch[p][x]; if(l[q]==l[p]+1) f[np]=q; else{ int nq=++cnt; l[nq]=l[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); f[nq]=f[q]; f[q]=f[np]=nq; for(;ch[p][x]==q;p=f[p]) ch[p][x]=nq; } }}inline void build(){ for(int i=0;i
             
              =0;i--) c[i]+=c[i+1]; for(int i=1;i<=cnt;i++) a[c[l[i]]--]=i;}inline void solve(){ for(int i=1;i<=cnt;i++){ int now=a[i]; siz[f[now]]+=siz[now]; r[f[now]]=max(r[f[now]],r[now]); if(l[now]&&siz[now]>=m){ if(l[now]>ans) ans=l[now],pos=r[now]; else if(ans==l[now]&&r[now]>pos) pos=r[now]; } }}int main(){ while(scanf("%d",&m)==1&&m){ scanf("%s",s),n=strlen(s); init(); build(); solve(); if(ans) printf("%d %d\n",ans,pos-ans); else puts("none"); } return 0;}