PAT 1005 字尾陣列

#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;
}