luogu2870 [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold

ref

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int nn, n, rnk[60005], tmp[60005], cnt[60005], m=128, p, saa[60005];

char s[15], ss[60005];

void sasort(){

	for(int i=0; i<m; i++)	cnt[i] = 0;

	for(int i=0; i<n; i++)	cnt[rnk[i]]++;

	for(int i=1; i<m; i++)	cnt[i] += cnt[i-1];

	for(int i=n-1; i>=0; i--)	saa[--cnt[rnk[tmp[i]]]] = tmp[i];

}

void getSuffixArray(){

	for(int i=0; i<n; i++){

		rnk[i] = ss[i];

		tmp[i] = i;

	}

	sasort();

	for(int j=1; p<n; j<<=1){

		p = 0;

		for(int i=n-j; i<n; i++)	tmp[p++] = i;

		for(int i=0; i<n; i++)

			if(saa[i]>=j)

				tmp[p++] = saa[i] - j;

		sasort();

		p = 1;

		swap(rnk, tmp);

		rnk[saa[0]] = 0;

		for(int i=1; i<n; i++)

			if(tmp[saa[i-1]]==tmp[saa[i]] && tmp[saa[i-1]+j]==tmp[saa[i]+j])

				rnk[saa[i]] = p - 1;

			else

				rnk[saa[i]] = p++;

		m = p;

	}

}

int main(){

	cin>>nn;

	for(int i=0; i<nn; i++){

		scanf("%s", s);

		ss[i] = ss[2*nn-i] = s[0];

	}

	n = nn * 2 + 1;

	getSuffixArray();

	int A=0, B=nn+1;

	while(A+B-nn-1<nn){

		if(rnk[A]<rnk[B])	printf("%c", ss[A++]);

		else	printf("%c", ss[B++]);

		if((A+B-nn-1)%80==0)	printf("\n");

	}

	return 0;

}