算法1

把字符串复制一份，然后直接用后缀数组解决

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;

const int N = 200010;
char s[N];
int x[N], y[N], c[N], sa[N], rk[N];
int n, m;

void get_sa()
{
    for(int i = 1; i <= n; ++ i) c[x[i] = s[i]] ++;
    for(int i = 2; i <= m; ++ i) c[i] += c[i - 1];
    for(int i = n; i; -- i) sa[c[x[i]] --] = i;
    for(int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for(int i = n - k + 1; i <= n; ++ i)
            y[++ num] = i;
        for(int i = 1; i <= n; ++ i)
            if(sa[i] > k)
                y[++ num] = sa[i] - k;
        for(int i = 1; i <= m; ++ i) c[i] = 0;
        for(int i = 1; i <= n; ++ i) c[x[i]] ++;
        for(int i = 2; i <= m; ++ i) c[i] += c[i - 1];
        for(int i = n; i; -- i) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for(int i = 2; i <= n; ++ i) 
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if(num == n) break;
        m = num;
    }
}

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; ++ i) s[i + n] = s[i];
    n *= 2;
    m = 300;
    get_sa();
    string res = "";
    for(int i = 1; i <= n; ++ i)
        if(sa[i] <= n / 2)
            printf("%c", s[sa[i] + n / 2 - 1]);
    return 0;
}