知识点: SA

原题面 Luogu

分析题意

SA 板子背诵检查。
断环成链，把字符串复制一遍扔到后面，跑 SA 即可。

代码实现

//知识点：SA
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#define ll long long
const int kMaxn = 2e5 + 10;
//=============================================================
int n, m, sa[kMaxn << 1], rk[kMaxn << 1], oldrk[kMaxn << 1];
char S[kMaxn];
int id[kMaxn], cnt[kMaxn], rkid[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
int cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && 
         oldrk[x + w] == oldrk[y + w];
}
//=============================================================
int main() { 
  scanf("%s", S + 1);
  n = strlen(S + 1), m = 1010;
  for (int i = n + 1; i <= 2 * n; ++ i) S[i] = S[i - n];
  n <<= 1;

  for (int i = 1; i <= n; ++ i) ++ cnt[rk[i] = S[i]];
  for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;

  for (int p, w = 1; w < n; w <<= 1) {
    p = 0;
    for (int i = n; i > n - w; -- i) id[++ p] = i;
    for (int i = 1; i <= n; ++ i) {
      if (sa[i] > w) id[++ p] = sa[i] - w;
    }

    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) ++ cnt[rkid[i] = rk[id[i]]];
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rkid[i]] --] = id[i];

    std :: swap(rk, oldrk);
    m = 0;
    for (int i = 1; i <= n; ++ i) {
      rk[sa[i]] = (m += (cmp(sa[i], sa[i - 1], w) ^ 1));
    }
  }
  for (int i = 1; i <= n; ++ i) {
    if (sa[i] <= n / 2)
    printf("%c", S[sa[i] + n / 2 - 1]);
  }
  return 0; 
}