但是，这样做最坏是 n^2 的。比如，给一个 AAAAAAAAAAA，我们每次都要判断两端取哪一个更优，这是 O(n) 的，需要做 n 次，复杂度爆炸。我们不得不考虑优化。我们发现，如果我们针对这种最劣情况，要是能用某种方法迅速找出两端相同的长度，就可以把最劣情况的每一次判断做到 logn，问题就解决了。你一定能想到，这个地方可以用哈希。
如果你不会哈希的基本操作的话，可以参考机房大佬的博客：lhm_的博客
```cpp
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#define N 500010
#define M 98244353
#define base 131
template<typename T> inline void read(T &x) {
x = 0; char c = getchar(); bool flag = false;
while (!isdigit(c)) {if (c == '-') flag = true; c = getchar(); }
while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
if (flag) x = -x;
}
using namespace std;
int n;
char s[N];
long long ha1[N], ha2[N], bas[N];
//因为要正着的串和反着的串比较，所以要用两个哈希
//bas[i]:base^i
char ans[N];
int top;
int lef, rig;//left, right
inline int che(int len) {//hash基本操作：比较两端是否相同
long long l = ((ha1[lef + len - 1] - ha1[lef - 1] * bas[len]) % M + M) % M;
long long r = ((ha2[rig - len + 1] - ha2[rig + 1] * bas[len]) % M + M) % M;
return l == r;
}
inline int halffind() {
int l = 1, r = (rig - lef + 1) >> 1;
int mid, res = 1;
while (l <= r) {
mid = (l + r) >> 1;
if (che(mid)) {
res = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return res;
}
int main() {
read(n);
for (register int i = 1; i < n; ++i) {
s[i] = getchar();
getchar();
}
s[n] = getchar();
bas[0] = 1;
for (register int i = 1; i <= n; ++i) {
ha1[i] = (ha1[i - 1] * base + s[i]) % M;
bas[i] = bas[i - 1] * base % M;
}
for (register int i = n; i; --i) {
ha2[i] = (ha2[i + 1] * base + s[i]) % M;
}
lef = 1, rig = n;
int len;
for (register int i = 1; i < n; ++i) {
if (s[lef] < s[rig]) {
ans[++top] = s[lef++];
} else if (s[rig] < s[lef]) {
ans[++top] = s[rig--];
} else {
len = halffind();
ans[++top] = s[lef + len] < s[rig - len] ? s[lef++] : s[rig--];
}
}
ans[n] = s[lef];//最后一个直接扔到答案结尾即可，不用判断
for (register int i = 1; i <= n; ++i) {
putchar(ans[i]);
if (i % 80 == 0) putchar('\n');
}
return 0;
}
```
第一次写题解，如果有错误，欢迎指出。