Best Cow Line

$\mathcal{PROBLEM}$

有 $n$ 个大写字母。现在可以进行 $n$ 次操作把原来的顺序中第一个或者最后一个字母剪贴到一个字符串的末尾。问这个字符串最小的字典序是什么。

$\texttt{Data Range: }\begin{aligned}\begin{matrix} & 1 \le n\le 2000\texttt{, Easy version. }\ \ \\ & 1 \le n\le 5\times 10^5\texttt{, Hard version.} \end{matrix}\end{aligned}$

$\mathcal{TIPS}$

似乎可以先考虑简单版本的贪心？

$\mathcal{SOLUTION}$

首先考虑简单版本的做法。

如果首字母和末字母不一样那么显然选择ASCII码小的那一个放到字符串末尾更为优秀。

那如果一样呢？那么就设两个指针 $p_1$ 和 $p_2$ 分别指向首字母和末字母，每一次如果一样就往中间同时移动两个指针，一直到不一样为止。这个时候选择字典序最小的那一个就可以了。

很遗憾，这个做法在全部都是同一个字符的时候时间复杂度是 $\mathcal O(n^2)$ 的，只能通过简单版。

发现这个东西在移动指针的时候很多次操作都是重复的。于是考虑二分。二分一个距离，然后判断如果移动了这个距离的时候是否已经出现过了两个相同的字符。很显然就是判断两个子串是否相等。这显然是一个后缀数组的板子题。当然也可以使用哈希进行处理。

时间复杂度如果使用哈希则是 $\mathcal O(n\log n)$ 的，如果使用后缀数组则是 $\mathcal O(n\log^2 n)$ 的。

$\mathcal{CODE}$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
char tmp[N];
using ull = unsigned long long;
ull h[N], hh[N], bit[N], base = 13331;
ull get_hash(int l, int r)
{
    return h[r] - h[l - 1] * bit[r - l + 1];
}
ull get_hash2(int l, int r)
{
    return hh[r] - hh[l - 1] * bit[r - l + 1];
}
signed main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> tmp[i];
    string s, t;
    s = ' ' + s;
    for (int i = 1; i <= n; i++)
        s += tmp[i];
    bit[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        bit[i] = bit[i - 1] * base;
        h[i] = h[i - 1] * base + s[i];
        hh[i] = hh[i - 1] * base + s[n - i + 1];
    }
    int p1 = 1, p2 = n, cnt = 1, tuola = 1;
    while (p1 <= p2)
    {
        if (s[p1] < s[p2]) t += s[p1++];
        else if (s[p1] > s[p2]) t += s[p2--];
        else
        {
            int l = 1, r = (p2 - p1 + 1) / 2, best = -1;
            while (l <= r)
            {
                int mid = l + r >> 1;
                int f1 = p1 + mid - 1, f2 = p2 - mid + 1;
                // [p1, f1] with [f2, p2]
                ull h1 = get_hash(p1, f1), h2 = get_hash2(n - p2 + 1, n - f2 + 1);
                if (h1 != h2)
                    best = mid, r = mid - 1;
                else
                    l = mid + 1;
            }
            // if (tuola == 15)
            //     cout << best << ' ' << s[p1 + best - 1] << ' ' << s[p2 - best + 1] << ' ' << get_hash(p1, p1 + best - 1) << ' ' << get_hash2(n - (p2 - best + 1), n - p2 + 1) << '\n';
            if (best == -1)
                t += s[p1++];
            else if (s[p1 + best - 1] < s[p2 - best + 1])
                t += s[p1++];
            else
                t += s[p2--];
        }
        if (cnt == 80)
        {
            cnt = 1;
            t += '\n';
        }
        else
            cnt++;
        tuola++;
    }
    cout << t << '\n';
    return 0;
}