LYDSY 1031

题目大意

暂无

题目解法

暂无

RTFC

#include <cstdio>
#include <cstring>
const int N = int(2e5 + 3);
char str[N];
int sa[N], rank[N], height[N], c[N];
template <typename T>
inline void swap(T &x, T &y)
{
    T t = x;
    x = y;
    y = t;
}
inline bool In_equal(const int *x, const int i, const int j, const int k, const int n)
{
    int ti = i + k < n ? x[i + k] : -1, tj = j + k < n ? x[j + k] : -1;
    return x[i] == x[j] && ti == tj;
}
int main()
{
    scanf("%s", str);
    int len = int(strlen(str));
    memcpy(str + len, str, len);
    len <<= 1;
    int *x = rank, *y = height, r = 256, yn;
    for (int i = 0; i < r; ++i) c[i] = 0;
    for (int i = 0; i < len; ++i) ++c[str[i]];
    for (int i = 1; i < r; ++i) c[i] += c[i - 1];
    for (int i = len - 1; i >= 0; --i) sa[--c[str[i]]] = i;
    r = 1;
    x[sa[0]] = 0;
    for (int i = 1; i < len; ++i)
        x[sa[i]] = str[sa[i]] == str[sa[i - 1]] ? r - 1 : r++;
    for (int k = 1; r < len; k <<= 1)
    {
        yn = 0;
        for (int i = len - k; i < len; ++i) y[yn++] = i;
        for (int i = 0; i < len; ++i)
            if (sa[i] >= k) y[yn++] = sa[i] - k;
        for (int i = 0; i < r; ++i) c[i] = 0;
        for (int i = 0; i < len; ++i) ++c[x[y[i]]];
        for (int i = 1; i < r; ++i) c[i] += c[i - 1];
        for (int i = len - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
        swap(x, y);
        r = 1;
        x[sa[0]] = 0;
        for (int i = 1; i < len; ++i)
            x[sa[i]] = In_equal(y, sa[i], sa[i - 1], k, len) ? r - 1 : r++;
    }
    for (int i = 0; i < len; ++i) rank[i] = x[i];
    for (int i = 0; i < len; i++)
        if (sa[i] < len >> 1)
            putchar(str[sa[i] + (len >> 1) - 1]);
    return 0;
}