如何设计最坏时间复杂度不超过nL²的算法判断是否存在循环旋转字符串对？

核心：用最小循环表示做统一匹配指纹 #

直接两两比对的复杂度是O(n²L)，完全超了题目要求的O(nL²)上限，本质是要找到一种等价标识，让同一循环旋转组的字符串标识完全一致，不同组的标识绝不混淆。

指纹的匹配逻辑 #

循环旋转是标准的等价关系，也就是说：

• 如果t是s的循环旋转，那么s也一定是t的循环旋转
• 两个同属一个旋转组的字符串，拥有完全一样的旋转结果集合

我们从这个集合里取字典序最小的那个循环旋转结果，作为整个组的唯一指纹：

1. 只要两个字符串互为循环旋转，它们的旋转集合完全重合，取出来的最小字典序串一定是同一个，指纹必然相等
2. 只要两个字符串的指纹相等，说明它们各自的旋转集合里都包含这个最小串，那两个字符串必然同属一个旋转组，也就是互为循环旋转

完全满足题目提示要求的“两串互为循环旋转当且仅当指纹相同”的性质。比如题目里的一对suffixsort和sortsuffix，它们的旋转集合完全一样，不管从哪个串开始算，找出来的最小字典序旋转串都是同一个值，一匹配就能识别出来。

指纹计算的具体步骤 #

对每个长度为L的输入字符串s，按以下方法算指纹：

• 先把s拼接自身得到临时串 t = s + s（长度固定为2L）

  这里的关键是：s的所有可能的循环旋转，都是t上从位置i（0 ≤ i < L）开始，截长度为L的子串，不存在遗漏。

• 遍历所有合法的起始位置i，对比对应的长度L的子串，找出字典序最小的那一个，直接把这个子串当s的指纹就行。

整体流程 #

• 建一个空的哈希表，键是算出来的指纹，值是对应的原字符串
• 依次遍历每个输入字符串：
  • 算出当前字符串的指纹
  • 查哈希表是否已经存在这个键：如果存在，直接取出表中对应的字符串，这就是我们要找的循环旋转对
  • 如果不存在，把当前指纹和对应字符串存入哈希表
• 全量遍历完都没找到重复键，就说明列表里没有符合要求的循环旋转对。

复杂度说明 #

• 就算用最朴素的方法找最小子串：单串要遍历L个起始位置，每个位置最多花L次字符比较判断字典序，单串计算开销是O(L²)，n个串总开销是O(nL²)，刚好卡到题目给的时间上限，完全符合要求。
• 如果换用专门求最小循环表示的Booth算法，单串的计算开销可以降到O(L)，整体复杂度能到O(nL)，比要求的效率更高。
• 因为我们的指纹是直接用真实的最小旋转字符串，不是带碰撞概率的模哈希，所以不存在误判，结果100%准确。

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