P1368 工艺 /【模板】最小表示法

2024-04-08 15:47:46

知识点: SA，线段树，单调栈

原题面 Luogu

题意简述

给定字符串 \(S\)，求其最小表示。
\(|S|\le 3\times 10^5\)。

分析题意

循环同构
当字符串 \(S\) 中可以选定一个位置 \(i\) 满足：

\[S[i:n]+S[1:i-1]=T \]

则称 \(S\) 与 \(T\) 循环同构。

字符串 \(S\) 的 最小表示 为与 \(S\) 循环同构的所有字符串中字典序最小的字符串。

最小表示法

考虑暴力，每次比较 \(i,j\) 开始的循环同构，\(k\) 为出现的第一个不同的位置。

若出现不一样的字符，跳过字典序较大的循环同构。
最后剩下的就是答案。

int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n) { //暴力比较
  if (a[(i + k) % n] == a[(j + k) % n]) {
    ++ k;
    continue ;
  }
  //跳过字典序较大的
  if (a[(i + k) % n] > a[(j + k) % n]) ++ i;
  else ++ j;
  k = 0; //清空 k
  if (i == j) i ++;
}
i = min(i, j);

看起来很快？
\(S=aaaa...aaaab\) 时，会被卡到 \(O(n^2)\)。

考虑奇怪的优化。
在上述匹配过程中，对于一对 \(i,j\)，若 \(k\) 为出现的第一个不同的位置，有：

\[S[i:i+k-1] = S[j:j+k-1] (k< n) \]

若 \(S[i+k] > S[j+k]\)，则对于 \(i\le l\le i + k\)，以 \(l\) 为起始位置的循环同构，一定不能成为答案。
用 \(S_x\) 表示以 \(x\) 为起始位置的循环同构，对于任意一个 \(S_{i+p}(p\le k)\) 一定存在 \(S_{j+p}\) 比他更优。

比较时可直接跳过下标区间 \([i,i+k]\)，直接比较 \(S_{i+k+1}\)。

\(k+1\) 的次数最多为 \(2n\)，时间复杂度 \(O(n)\)。

SA

复制一遍 \(S\)，放到原串后边。
离散化，跑 SA，答案即 \(rk\) 最小且 \(\le |S|\) 的后缀。

SAM

建 SAM，从根节点按字典序贪心，跑出一个长度为 \(n\) 的串即为答案。

代码实现

//知识点：最小表示法 
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
const int kMaxn = 3e5 + 10;
//=============================================================
int n, a[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 MinRep() {
  int i = 0, j = 1, k = 0;
  while (i < n && j < n && k < n) {
    int delta = a[(i + k) % n] - a[(j + k) % n];
    if (delta == 0) {
      ++ k;
      continue ;
    }
    if (delta > 0) i += k + 1;
    else j += k + 1;
    if (i == j) j ++;
    k = 0;
  }
  return std :: min(i, j);
}
//=============================================================
int main() {
  n = read();
  for (int i = 0; i < n; ++ i) a[i] = read();
  for (int i = MinRep(), j = 0; j < n; ++ j) {
    printf("%d ", a[(i + j) % n]);
  }
  return 0;
}

码农公寓