#include <iostream>
#include <cstring>
using namespace std;
struct SuffixArray{//后綴陣列
#ifndef _SA_
#define maxn 1200000
#define maxcnt 270
#endif
int n; //字串長度
int sa[maxn]; //后綴陣列, 排名為i的后綴的位置
int rk[maxn]; //名次陣列，第i個位置開始的后綴排名
int ssa[maxn]; //保留后綴陣列
int srk[maxn]; //保留名次陣列
int cnt[maxn]; //計數陣列
int height[maxn]; //排名相鄰的兩個后綴的最長公共前綴
void doubling(string s, int m)//倍增法計算后綴陣列
{
//根據第一關鍵字進行基數排序
memset(cnt, 0, sizeof(cnt));
for(int i=0; i<s.length(); ++i) ++cnt[ rk[i] = s[i] ];
for(int i=1; i<m; ++i) cnt[i] += cnt[i-1];
for(int i=s.length()-1; i>=0; --i) sa[ --cnt[s[i]] ] = i;
for(int j=1, kk=1; kk < s.length(); j<<=1, m=kk)
{
//根據第二關鍵字進行基數排序，ssa為根據第二關鍵字排序后的后綴陣列
int i;
for(i=s.length()-j, kk=0; i < s.length(); ++i) ssa[kk++] = i;
for(i=0; i < s.length(); ++i) if(sa[i] >= j) ssa[kk++] = sa[i] - j;
//根據第一關鍵字進行基數排序
for(i=0; i < s.length(); ++i) srk[i] = rk[ssa[i]];
memset(cnt, 0, sizeof(cnt));
for(i=0; i<s.length(); ++i) ++cnt[ srk[i] ];
for(i=1; i<m; ++i) cnt[i] += cnt[i-1];
for(i=s.length()-1; i>=0; --i) sa[ --cnt[srk[i]] ] = ssa[i];
memcpy(srk, rk, sizeof(rk));
for( rk[sa[0]] = 0, kk = 1, i = 1; i < s.length(); ++i )
{
rk[sa[i]] = (srk[sa[i-1]] == srk[sa[i]] && sa[i-1] + j < s.length() && sa[i] + j < s.length() && srk[sa[i-1] + j] == srk[sa[i] + j] )?kk-1:kk++;
}
}
}
void generateHeight(string s)//計算后綴最長公共前綴
{
int i, j, kk = 0;
// for(i=0; i<s.length(); ++i) rk[sa[i]] = i;
for(i=0; i<s.length(); height[rk[i++]] = kk)
{
if(rk[i]) for(kk?kk--:0, j = sa[rk[i]-1]; i+kk < s.length() && j+kk < s.length() && s[i+kk] == s[j+kk]; ++kk);
}
}
};
static SuffixArray sa;
int main()
{
ios::sync_with_stdio(false);
int N;
string s;
cin>>N;
getline(cin, s);
getline(cin, s);
sa.doubling(s, 130);
sa.generateHeight(s);
// for(int i=0; i<s.length(); ++i) cout<<sa.height[i]<<endl;//測驗
int idx = sa.sa[0], ans = 0, maxL = 0;
for(int i=1; i<s.length(); ++i)
{
if(sa.height[i]>=N)
{
ans++;
}
else
{
ans = 0;
}
if(ans > maxL && s.length()-sa.sa[i] >= N)
{
maxL = ans;
idx = sa.sa[i];
}
}
cout<<s.substr(idx, N)<<" "<<maxL+1<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/152859.html
標籤：區塊鏈