SB题

解决环状的问题 把整个序列复制一遍是手筋

懵逼的 题目

传送至 Bilibili

扯淡的 题解

唉…突然想起来当年我bzoj想做的第二道题就是这个…第一道是(想用EK做)狼抓兔子2333那时候好像想直接推出末尾的字符然后排序来着吧…唉…

今天本来想整理一下板子来着…结果先是MHR的锅++奇怪矩阵…又是Asia基本等于没讲的凸包…还有Diesheep和SLR的卖萌 + 卖弱…

so sad…

正好看着SA还不怎么会来着…于是搞了一波height…然后在CA爷爷的一句话题解里挑了个SA秒了…

这个题…连Height都不用求感觉非常资瓷啊

你只需要把整个序列都复制一遍, 然后求出所有后缀的排名即可, 这样就相当于给环上所有可能的字符串排序了…然后…输出就行了…

主要判断SA[i] <= (n >> 1)的时候才输出…因为排序的时候后面复制的串可能会排在前面…

要是SDOI的字符串也这么良心就好了…祈祷.jpg

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (200000 + 5)
using namespace std;
int n, a[MAXN], tmp[MAXN], rnk[MAXN], sa[MAXN], fir[MAXN], sec[MAXN], tong[MAXN];
char s[MAXN], sors[MAXN];
void initsa()
{
    for (int i = 1; i <= n; i++)    ++tong[a[i]];
    for (int i = 1; i <= n; i++)    tong[i] += tong[i - 1];
    for (int i = 1; i <= n; i++)    rnk[i] = tong[a[i] - 1] + 1;

    for (int t = 1; t <= n; t <<= 1)
    {
        for (int i = 1; i <= n; i++)    fir[i] = rnk[i];
        for (int i = 1; i <= n; i++)    sec[i] = ((i + t > n) ? 0 : rnk[i + t]);

        fill(tong, tong + n + 1, 0);
        for (int i = 1; i <= n; i++)    ++tong[sec[i]];
        for (int i = 1; i <= n; i++)    tong[i] += tong[i - 1];
        for (int i = 1; i <= n; i++)    tmp[n - --tong[sec[i]]] = i;

        fill(tong, tong + n + 1, 0);
        for (int i = 1; i <= n; i++)    ++tong[fir[i]];
        for (int i = 1; i <= n; i++)    tong[i] += tong[i - 1];
        for (int j = 1, i; j <= n; j++)    i = tmp[j], sa[tong[fir[i]]--] = i;

        bool ok = true;
        for (int j = 1, last = 0, i; j <= n; j++)
        {
            i = sa[j];
            if (!last)    rnk[i] = 1;
            else if (fir[i] == fir[last] && sec[i] == sec[last])    rnk[i] = rnk[last], ok = false;
            else    rnk[i] = rnk[last] + 1;
            last = i;
        }
        if (ok)    break;
    }
}
int main()
{
    scanf("%s", s);
    n = strlen(s);
    strcpy(sors, s);
    for (int i = n; i < (n << 1); i++)
        s[i] = s[i - n];
    sort(sors, sors + n);
    n <<= 1;
    int tn = unique(sors, sors + n) - sors - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(sors, sors + tn, s[i - 1]) - sors + 1;
    initsa();
    for (int i = 1; i <= n; i++)
        if (sa[i] <= (n >> 1))
            printf("%c", sors[a[sa[i] + (n >> 1) - 1] - 1]);
    return 0;
}

// I0O7SJ
// 1234: 1234 2341 32

By 沙茶 Cansult