题意

题目链接：P2870 [USACO07DEC]Best Cow Line G

分析

容易想到贪心处理，尽可能选首尾字符中较小的那个；而当它们相等的时候，就需要比较第二个和倒数第二个，才能按最优策略实现；若还相等，就递归进行下去。

这其实就是在对字符串比大小——一段后缀和一段反串的后缀。

这就是比较两个后缀的大小，容易联想到后缀数组。而要使用后缀数组，只需要把反串接在原串后面，并在接缝处插入一个无穷小的字符（其实只需要比原串中的所有字符小即可），然后在新串上直接求后缀数组即可。

为什么要插入一个无穷小的字符？它相当于一个结尾标识，有了它，等价于接在原串后面的反串不会被算入原串的后缀中。如果不理解可以手动模拟。

需要注意的是洛谷 #22 是个 hack 点，容易 TLE，而且最近洛谷评测机日常波动，所以要优化细节卡常。具体卡常技巧可以参考 oi-wiki 。

源码

const int N = 2*(5e5+5);
#define gc getchar

int n, w;
char s[N];
int sa[N], rk[N<<1], oldrk[N<<1], cnt[N], id[N], p[N]; 

inline bool cmp(int x, int y, int j) {
	return oldrk[x] == oldrk[y] && oldrk[x+j] == oldrk[y+j];
}

int main()
{	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		s[i] = gc();
		while (s[i] < 'A' || s[i] > 'Z') s[i] = gc();
		s[(n<<1)-i+2] = s[i];
	}
	s[n+1] = 'A' - 1;//赋值为极小, 避免对后缀排序产生影响 
	n = (n<<1)+1;
	
	for (int i = 1; i <= n; i++) cnt[(int)s[i]]++;
	w = 'Z'+5;
	for (int i = 1; i <= w; i++) cnt[i] += cnt[i-1];
	for (int i = n; i >= 1; i--) sa[cnt[(int)s[i]]--] = i;
	w = 0;
	for (int i = 1; i <= n; i++)
		rk[sa[i]] = s[sa[i]] == s[sa[i-1]] ? w : ++w;
	
	for (int j = 1; j < n; j <<= 1) {
		int t = 0;
		for (int i = n; i > n - j; i--) id[++t] = i;
		for (int i = 1; i <= n; i++)
			if (sa[i] > j) id[++t] = sa[i] - j;
		
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; i++) cnt[p[i] = rk[id[i]]]++;
		for (int i = 1; i <= w; i++) cnt[i] += cnt[i-1];
		for (int i = n; i >= 1; i--) sa[cnt[p[i]]--] = id[i];
		
		memcpy(oldrk, rk, sizeof(oldrk));
		w = 0;
		for (int i = 1; i <= n; i++)
			rk[sa[i]] = cmp(sa[i-1], sa[i], j) ? w : ++w;
	}
	
	int l = 1, r = (n-1)>>1, tot = 0;
	while (l <= r) {
		printf("%c", rk[l] < rk[n-r+1] ? s[l++] : s[r--]);
		if (++tot % 80 == 0) printf("\n");
	}
	return 0;
}

暴力做法就是每次最坏 𝑂(𝑛) O(n) 地判断当前应该取首还是尾（即比较取首得到的字符串与取尾得到的反串的大小），只需优化这一判断过程即可．

由于需要在原串后缀与反串后缀构成的集合内比较大小，可以将反串拼接在原串后，并在中间加上一个没出现过的字符（如 #，代码中可以直接使用空字符），求后缀数组，即可 𝑂(1) O(1) 完成这一判断．

#include <cctype>
#include <cstring>
#include <iostream>
using namespace std;

constexpr int N = 1000010;

char s[N];
int n, sa[N], id[N], oldrk[N * 2], rk[N * 2], px[N], cnt[N];

bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

int main() {
  int i, w, m = 200, p, l = 1, r, tot = 0;

  cin >> n;
  r = n;

  for (i = 1; i <= n; ++i)
    while (cin >> s[i], !isalpha(s[i]));
  for (i = 1; i <= n; ++i)
    rk[i] = rk[2 * n + 2 - i] = s[i];  // 拼接正反两个字符串，中间空出一个字符

  n = 2 * n + 1;
  // 求后缀数组
  for (i = 1; i <= n; ++i) ++cnt[rk[i]];
  for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

  for (w = 1; w < n; w *= 2, m = p) {  // m=p 就是优化计数排序值域
    for (p = 0, i = n; i > n - w; --i) id[++p] = i;
    for (i = 1; i <= n; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }
  // 利用后缀数组O(1)进行判断
  while (l <= r) {
    cout << (rk[l] < rk[n + 1 - r] ? s[l++] : s[r--]);
    if ((++tot) % 80 == 0) cout << '\n';  // 回车
  }

  return 0;
}