寻找判断字符串指定旋转是否为字典序最小的O(n)直观算法

当然存在，这里有个直观且简洁的线性时间方案：

假设原字符串为 S（长度为 n），给定的旋转结果是 T（若 T 不是 S 的旋转，直接判定为「不是最小旋转」）。我们可以利用字符串拼接的特性：将 S 拼接为 S+S 后，S 的所有旋转结果都是这个拼接串中长度为 n 的连续子串。

验证步骤如下：

• （可选前置检查）确认 T 是 S 的旋转：检查 T 是否是 S+S 的子串且长度为 n，这一步可通过线性时间的字符串匹配算法完成（比如KMP），若输入已保证 T 是旋转则可跳过。
• 核心验证：我们需要确认 T 是 S+S 中所有长度为 n 的子串里字典序最小的那个。为了线性时间完成，我们可以通过一次遍历剪枝实现：
  1. 初始化当前最小子串的起始位置 min_pos = 0（对应原串 S）。
  2. 遍历 S+S 中所有可能的旋转起始位置 i（范围 1 ≤ i < n）：
     • 从位置 0 开始，比较 S+S[min_pos + k] 和 S+S[i + k]（k 从0开始递增），直到找到第一个不同的字符。
     • 若 S+S[i + k] < S+S[min_pos + k]，则更新 min_pos = i，同时跳过后续 k 个位置（因为这些位置的子串开头和当前 i 对应的子串一致，不可能更小）。
     • 若 S+S[i + k] > S+S[min_pos + k]，直接跳过后续 k 个位置。
  3. 最后提取 S+S[min_pos:min_pos+n]，判断是否与 T 完全相等：相等则 T 是最小旋转，否则不是。

这个方案比传统的最小旋转查找算法（比如Booth算法）简洁很多，核心是通过剪枝避免了重复的字符比较，整个过程仅需线性时间O(n)，逻辑直观易懂。

内容的提问来源于stack exchange，提问作者David Pellow