123-字符串-最小表示法

核心概述

最小表示法用于在循环等价类中选出字典序最小的旋转，通过在 s+s 上的双指针比较避免重复回溯，实现 O(n) 求解。

原文引述

Description: Find the lexicographically minimal rotation of a string. Works by comparing substrings of s+s using two pointers in O(n). Returns the starting index of the minimal rotation. Time: O(n) Status: tested ——摘自本节点现有英文注释

展开阐述

• 定义与背景

  • 目标：对循环串选择字典序最小的表示，常用于循环同构比较、规范化。
  • 思路：构造 t=s+s，在两个候选起点 i、j 上以 k 为偏移比较，任一方落后则跳过其前缀区间。

• 接口/字段/数据结构与输入输出语义（按仓库约定）

  • 典型接口（据约定风格）：
    • int minRepresentation(const string& s)
      • 返回最小表示的起始位置 idx（0-index）。
    • string minimalRotation(const string& s)
      • 返回最小表示字符串（可由 s.substr(idx) + s.substr(0, idx) 构造）。
  • 输出语义：
    • 若存在多个最小起点，算法返回字典序最小的起点（唯一）。

• 核心流程与关键要点（双指针）

  1. 令 t = s + s（长度 2n）。
  2. 初始化 i=0, j=1, k=0。
  3. while (i < n && j < n && k < n)：
     • 若 t[i+k] == t[j+k]：k++。
     • 若 t[i+k] > t[j+k]：i = i + k + 1；若 i ≤ j 则 i = j + 1；k = 0。
     • 若 t[i+k] < t[j+k]：j = j + k + 1；若 j ≤ i 则 j = i + 1；k = 0。
  4. 返回 min(i, j)。
  • 正确性要点与不变式：
    • 每次比较至少丢弃一个不可能成为最优起点的前缀区间，总推进不回退，保证线性次比较。

• 复杂度与边界条件

  • 时间 O(n)，空间 O(1)。
  • 边界：空串或单字符串直接返回 0；字符集仅需全序比较。

• 与相邻技术的取舍对比

  • 与后缀数组：亦可通过 SA 求最小表示，但通常为 O(n log n)（见 124-字符串-后缀数组）。
  • 与哈希：可用哈希与二分比对子串，但整体复杂度与实现细节不如本法直观（见 119-字符串-字符串哈希、120-字符串-Codeforces哈希）。

关联节点

• 124-字符串-后缀数组
• 125-字符串-后缀树
• 119-字符串-字符串哈希
• 120-字符串-Codeforces哈希