最小表示法

问题

找到一个字符串的所有循环位移中最小的那个。

方法

双指针，假设当前两个串分别从 $i$ 和 $j>i$ 开始，暴力找出它们第一个不同的位置，设它到每个串开头的距离是 $k$。

• 如果 $s[i+k]>s[j+k]$，说明当前找到的这个串 $j$ 没用。并且 $j$ 到 $j+k$ 之间的点也不能作为起点；
• 如果 $s[i+k]<s[j+k]$，说明当前找到的串 $i$ 没用。并且 $i$ 到 $i+k$ 之间的点也不能作为起点；
• 没有第三种可能。

所以，$i$ 和 $j$ 移动的总距离都不超过 $n$，时间复杂度是 $O(n)$。

相关题目

LC1163 - 按字典序排在最后的子串