我的代码没空字符，但是过了。
[记录](https://www.luogu.com.cn/record/105071005)
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int L = 1000000;
int ls;
char s[L + 5];
void init()
{
scanf("%d", &ls);
for(int i = 1; i <= ls; i++)
{
scanf(" %c", &s[i]);
}
}
int sa[L + 5], rk[L + 5];
int id[L + 5], ork[L * 2 + 5];
int cnt[L + 5];
void getSA()
{
for(int i = 1; i <= ls; i++)
{
cnt[(int)s[i]]++;
}
int P = L;
for(int i = 1; i <= P; i++)
{
cnt[i] += cnt[i - 1];
}
for(int i = ls; i >= 1; i--)
{
sa[cnt[(int)s[i]]--] = i;
}
for(int i = 1; i <= P; i++)
{
cnt[i] = 0;
}
int p = 0;
for(int i = 1; i <= ls; i++)
{
if(i == 1 || s[sa[i]] != s[sa[i - 1]])
{
rk[sa[i]] = ++p;
}
else
{
rk[sa[i]] = p;
}
}
P = p;
for(int len = 2; len <= ls * 2; len <<= 1)
{
int mid = len >> 1;
p = 0;
for(int i = ls - mid + 1; i <= ls; i++)
{
id[++p] = i;
}
for(int i = 1; i <= ls; i++)
{
if(sa[i] > mid)
{
id[++p] = sa[i] - mid;
}
}
for(int i = 1; i <= ls; i++)
{
cnt[rk[id[i]]]++;
}
for(int i = 1; i <= P; i++)
{
cnt[i] += cnt[i - 1];
}
for(int i = ls; i >= 1; i--)
{
sa[cnt[rk[id[i]]]--] = id[i];
}
for(int i = 1; i <= P; i++)
{
cnt[i] = 0;
}
for(int i = 1; i <= ls; i++)
{
ork[i] = rk[i];
}
p = 0;
for(int i = 1; i <= ls; i++)
{
if(i == 1 || !(ork[sa[i]] == ork[sa[i - 1]] && ork[sa[i] + mid] == ork[sa[i - 1] + mid]))
{
rk[sa[i]] = ++p;
}
else
{
rk[sa[i]] = p;
}
}
P = p;
}
}
char ans[L + 5];
int cntC;
void solve()
{
// for(int i = 1; i <= ls; i++)
// {
// printf("%c ", s[i]);
// }
for(int i = ls + 1; i <= ls * 2; i++)
{
s[i] = s[ls - (i - ls) + 1];
}
ls *= 2;
getSA();
// for(int i = 1; i <= ls; i++)
// {
// printf("%d ", rk[i]);
// }
// printf("\n");
int l = 1, r = ls / 2;
while(l <= r)
{
if(rk[l] <= rk[ls - r + 1])
{
ans[++cntC] = s[l++];
}
else
{
ans[++cntC] = s[r--];
}
}
for(int i = 1; i <= ls / 2; i++)
{
printf("%c", ans[i]);
if(i % 80 == 0)
{
printf("\n");
}
}
}
int main()
{
init();
solve();
return 0;
}
```
by cmaths @ 2023-03-18 16:31:40
这题可能没必要，有些要用到height的时候防止俩字符串合成一个不可能的子串
by xu826281112 @ 2023-07-21 00:15:38