https://vjudge.net/problem/UVALive-4513
终于做出来了。。。。。。。。。
各种sb错误，最后对拍出来了，还没改对。。。。。。。。。。。。。。。。。。。。。
快半天的时间。。。。。。。。。。
看上去第一眼就猜出了一个结论：这些相同的字符串肯定是按后缀排序的顺序存在的。
于是就想出了一个方法：求出sa和lcp，然后扫描每个长为m的区间，rmq其中最小的lcp和最大的sa作为答案（扫描是指枚举左端点，右端点是左端点+m-2）
这样复杂度nlogn，可以接受，用单调队列？（不清楚，没学好），于是我用了线段树。
（请无视）然后各种wa，各种改，搞得我怀疑自己的方法是错的，然后看了看题解，好像都是二分判定。再想了想，貌似是对的，但是不确定，就翻了翻别人的代码，看见和自己的想法差不多，就确定是对的了，然后就各种调试，看见一个又一个sb错误：update1和update搞反找了半天。。。然后又对拍拍了半天拍出来了组错误数据，发现sa[0]=0这样的串会错，于是就改掉，对了。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 80010
struct data
{
int val,pos;
};
int n,m,k;
char s[N];
int Rank[N],sa[N],temp[N],lcp[N],tree[N<<],tree1[N<<];
bool cp(int i,int j)
{
if(Rank[i]!=Rank[j]) return Rank[i]<Rank[j];
int ri=i+k<n?Rank[i+k]:-;
int rj=j+k<n?Rank[j+k]:-;
return ri<rj;
}
void update(int l,int r,int x,int pos,int num)
{
if(l==r)
{
tree[x]=num;
return;
}
if(pos>(l+r)/) update((l+r)/+,r,x*+,pos,num);
else update(l,(l+r)/,x*,pos,num);
tree[x]=min(tree[x*],tree[x*+]);
}
int query(int l,int r,int x,int a,int b)
{
if(l>b||r<a) return N;
if(l>=a&&r<=b) return tree[x];
int i=query(l,(l+r)/,x*,a,b);
int j=query((l+r)/+,r,x*+,a,b);
return min(i,j);
}
void update1(int l,int r,int x,int pos,int Pos)
{
if(l==r)
{
tree1[x]=Pos;
return;
}
if(pos>(l+r)/) update1((l+r)/+,r,x*+,pos,Pos);
else update1(l,(l+r)/,x*,pos,Pos);
tree1[x]=max(tree1[x*],tree1[x*+]);
}
int query1(int l,int r,int x,int a,int b)
{
if(l>b||r<a) return -N;
if(l>=a&&r<=b) return tree1[x];
int i=query1(l,(l+r)/,x*,a,b);
int j=query1((l+r)/+,r,x*+,a,b);
return max(i,j);
}
void Sa()
{
n=strlen(s);
for(int i=;i<n;i++)
{
Rank[i]=s[i]; sa[i]=i;
}
for(k=;k<=n;k*=)
{
sort(sa,sa+n,cp);
temp[sa[]]=;
for(int i=;i<n;i++) temp[sa[i]]=temp[sa[i-]]+(cp(sa[i-],sa[i]));
for(int i=;i<n;i++) Rank[i]=temp[i];
}
}
void Lcp()
{
n=strlen(s);
for(int i=;i<n;i++) Rank[sa[i]]=i;
int h=;
for(int i=;i<n;i++)
{
int j=sa[Rank[i]-];
if(Rank[i]<=) continue;
if(h>) h--;
for(;((i+h<n)&&(j+h<n));h++)
{
if(s[i+h]!=s[j+h]) break;
}
lcp[Rank[i]-]=h;
}
update1(,n,,,sa[]);
for(int i=;i<n-;i++)
{
update(,n,,i+,lcp[i]);
update1(,n,,i+,sa[i+]);
}
}
void solve()
{
memset(sa,,sizeof(sa));
memset(lcp,,sizeof(lcp));
memset(tree,0x3f3f,sizeof(tree));
memset(tree1,,sizeof(tree1));
memset(Rank,,sizeof(Rank));
Sa(); Lcp();
int l=;
data ans; ans.val=; ans.pos=;
for(int i=;i+m-<n;i++)
{
data x;
x.val=query(,n,,i,i+m-);
x.pos=query1(,n,,i,i+m-);
if(x.val>ans.val||(x.val==ans.val&&x.pos>ans.pos))
{
ans.val=x.val;
ans.pos=x.pos;
}
}
if(ans.val==) printf("none\n");
else printf("%d %d\n",ans.val,ans.pos);
}
int main()
{
while()
{
scanf("%d",&m);
if(!m) break;
scanf("%s",s);
if(m==)
{
printf("%d %d\n",strlen(s),);
continue;
}
n=strlen(s);
solve();
}
return ;
}