题目链接：
1005 Programming Pattern (35分)
思路：
有两种做法（见标题）
1.第一种做法我们得到后缀数组和高度数组后，需要转变一下思维，求长度为N、出现频率最高、字典序最小的子串，我们观察高度数组可以发现，如果有连续的k个h[i]>=N，那必定有k+1个这样的子串，将k记录下来；从前往后遍历，由于本身已经按字典序排好序，我们之后找到另一个k大于先前记录的k就进行更新；
（在计算后缀数组时需要基数排序，用快排会超时）
2.字符串哈希做法之后有空补。。
代码(后缀数组)：
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1048576+50;
char s[maxn];
int n,sa[maxn],cnt[maxn],t1[maxn],t2[maxn],rk[maxn],lcp[maxn];
void cal_sa(){
int m=127;
int i,*x=t1,*y=t2;
for(int i=0;i<m;++i) cnt[i]=0;
for(int i=0;i<n;++i) ++cnt[x[i]=s[i]];
for(int i=1;i<m;++i) cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;--i) sa[--cnt[x[i]]]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
for(i=n-k;i<n;++i) y[p++]=i;
for(i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;++i) cnt[i]=0;
for(i=0;i<n;++i) ++cnt[x[y[i]]];
for(i=1;i<m;++i) cnt[i]+=cnt[i-1];
for(i=n-1;i>=0;--i) sa[--cnt[x[y[i]]]]=y[i];
swap(x,y);
p=1; x[sa[0]]=0;
for(i=1;i<n;++i) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n) break; m=p;
}
}
void cal_lcp(){
for(int i=0;i<n;++i) rk[sa[i]]=i;
int h=0; lcp[0]=0;
for(int i=0;i<n;++i){
int j=sa[rk[i]-1];
if(h) --h;
while(j+h<n&&i+h<n&&s[j+h]==s[i+h]) ++h;
lcp[rk[i]-1]=h;
}
}
int len;
void solve(){
n=strlen(s); cal_sa(); cal_lcp();
int cnt=0,res; int ans=1;
for(int i=0;i<=n;++i){
if(lcp[i]>=len) ++ans;
else ans=1;
if(sa[i]+len<=n&&cnt<ans) cnt=ans,res=sa[i];
}
for(int i=0;i<len;i++) putchar(s[res+i]); printf(" %d",cnt);
}
int main(){
scanf("%d",&len); while(getchar()==' ');
cin.getline(s,maxn);
solve();
return 0;
}