跳转至

# 最小表示法

## 定义

最小表示法是用于解决字符串最小表示问题的方法．

## 字符串的最小表示

### 循环同构

当字符串 𝑆 S 中可以选定一个位置 𝑖 i 满足

𝑆[𝑖⋯𝑛]+𝑆[1⋯𝑖−1]=𝑇 S[i⋯n]+S[1⋯i−1]=T

则称 𝑆 S 与 𝑇 T 循环同构

### 最小表示

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

## simple 的暴力

我们每次比较 𝑖 i 和 𝑗 j 开始的循环同构，把当前比较到的位置记作 𝑘 k，每次遇到不一样的字符时便把大的跳过，最后剩下的就是最优解．

### 实现

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    int k = 0, i = 0, j = 1;
    while (k < n && i < n && j < n) {
      if (sec[(i + k) % n] == sec[(j + k) % n]) {
        ++k;
      } else {
        if (sec[(i + k) % n] > sec[(j + k) % n])
          ++i;
        else
          ++j;
        k = 0;
        if (i == j) i++;
      }
    }
    i = min(i, j);

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    k, i, j = 0, 0, 1
    while k < n and i < n and j < n:
        if sec[(i + k) % n] == sec[(j + k) % n]:
            k += 1
        else:
            if sec[(i + k) % n] > sec[(j + k) % n]:
                i += 1
            else:
                j += 1
            k = 0
            if i == j:
                i += 1
    i = min(i, j)

### 解释

该实现方法随机数据下表现良好，但是可以构造特殊数据卡掉．

例如：对于 𝚊 𝚊 𝚊⋯𝚊 𝚊 𝚋 aaa⋯aab, 不难发现这个算法的复杂度退化为 𝑂(𝑛 2)O(n 2)．

我们发现，当字符串中出现多个连续重复子串时，此算法效率降低，我们考虑优化这个过程．

## 最小表示法

### 算法核心

考虑对于一对字符串 𝐴,𝐵 A,B, 它们在原字符串 𝑆 S 中的起始位置分别为 𝑖,𝑗 i,j, 且它们的前 𝑘 k 个字符均相同，即

𝑆[𝑖⋯𝑖+𝑘−1]=𝑆[𝑗⋯𝑗+𝑘−1]S[i⋯i+k−1]=S[j⋯j+k−1]

不妨先考虑 𝑆[𝑖 +𝑘] >𝑆[𝑗 +𝑘]S[i+k]>S[j+k] 的情况，我们发现起始位置下标 𝑙 l 满足 𝑖 ≤𝑙 ≤𝑖 +𝑘 i≤l≤i+k 的字符串均不能成为答案．因为对于任意一个字符串 𝑆 𝑖+𝑝 S i+p（表示以 𝑖 +𝑝 i+p 为起始位置的字符串，𝑝 ∈[0,𝑘]p∈[0,k]）一定存在字符串 𝑆 𝑗+𝑝 S j+p 比它更优．

所以我们比较时可以跳过下标 𝑙 ∈[𝑖,𝑖 +𝑘]l∈[i,i+k], 直接比较 𝑆 𝑖+𝑘+1 S i+k+1

这样，我们就完成了对于上文暴力的优化．

### 时间复杂度

𝑂(𝑛)O(n)

### 过程

1. 初始化指针 𝑖 i 为 0 0，𝑗 j 为 1 1；初始化匹配长度 𝑘 k 为 0 0
2. 比较第 𝑘 k 位的大小，根据比较结果跳转相应指针．若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同
3. 重复上述过程，直到比较结束
4. 答案为 𝑖,𝑗 i,j 中较小的一个

### 实现

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    int k = 0, i = 0, j = 1;
    while (k < n && i < n && j < n) {
      if (sec[(i + k) % n] == sec[(j + k) % n]) {
        k++;
      } else {
        sec[(i + k) % n] > sec[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
        if (i == j) i++;
        k = 0;
      }
    }
    i = min(i, j);

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    k, i, j = 0, 0, 1
    while k < n and i < n and j < n:
        if sec[(i + k) % n] == sec[(j + k) % n]:
            k += 1
        else:
            if sec[(i + k) % n] > sec[(j + k) % n]:
                i = i + k + 1
            else:
                j = j + k + 1
            if i == j:
                i += 1
            k = 0
    i = min(i, j)

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, partychicken, StudyingFather, countercurrent-time, Early0v0, Enter-tainer, H-J-Granger, iamtwz, NachtgeistW, Suyun514, Xeonacid, AngelKitty, CCXXXI, cjsoft, diauweb, ezoixx130, fjzzq2002, GavinZhengOI, GekkaSaori, Gesrua, Junyan721113, karin0, Konano, ksyx, kxccc, LovelyBuggies, lychees, Makkiy, Menci, mgt, minghu6, P-Y-Y, Peanut-Tang, PotassiumWings, SamZhangQingChuan, shawlleyw, sshwy, SukkaW, Tiphereth-A, TrisolarisHD, weiyong1024
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用