找出与 \(S\) 循环同构的字符串中字典序最小的那一个。
记录两个指针 \(i\) 和 \(j\)，表示当前可能成为答案的最前面两个位置。初值为字符串的前两个位置 \(1\) 和 \(2\)。每次按 \(k\) 从小到大暴力比较 \(S_{i+k}\) 和 \(S_{j+k}\) 的大小，当遇到 \(S_{i+k}>S_{j+k}\) 时，\(i\sim i+k\) 可以直接跳过。因为以位置 \(i+p(p\leq k)\) 开头的字符串一定比以位置 \(j+p\) 开头的字符串字典序大。\(S_{j+k}>S_{i+k}\) 同理。
根据定义，如果前面那个指针不优了，那至少会跳到后面那个指针后面一个位置。这样也就不会出现两个指针相等的情况。
但当 \(k>n\) 时，这两个位置是否就是字典序最小的呢？答案是肯定的，假设 \(i<j\)，因为 \(1\sim i-1\) 和 \(i+1\sim j-1\) 都不优，而循环节长度至多也只有 \(j-i\)。
标签：位置,最小,笔记,表示法,字符串,字典,指针 From： https://www.cnblogs.com/landsol/p/17804653.html