假设我们有一个字符串 \(s\)，下标从 \(1\) 到 \(n\)，我们将字符串复制一遍接在尾部，设新的字符串为 \(ss\)，对于 \(1\leq i \leq n\) 显然有 \(ss_i=ss_{i+n}\)。
对于 \(1\leq i \leq n\)，\(ss\) 中 \(i\) 到 \(i+n-1\) 可以构成一个长度为 \(n\) 的字符串，所有这些字符串中最小的称为 \(s\) 的最小表示。
正常暴力求法：求出所有字符串，暴力判断字典序。复杂度 \(O(n^2)\)。
但是！这里有一种 \(O(n)\) 的算法。
设变量 \(i,j\) 表示当前比对的两个字符串在 \(ss\) 中的开头位置，初始 \(i=1\),\(j=2\)。
我们还是暴力比对两个字符串，设第 \(i+k\) 位不同。（两个字符串完全相同直接结束就行了，因为只有可能是循环节）
假设是 \(ss_{i+k}\) 比 \(ss_{j+k}\) 打，则 \(i\) 可以直接等于 \(i+k+1\)。
证明一下：假设 \(i+p\) 是 \(i\) 与 \(i+k+1\) 中间的一位，那 \(j+p\) 开始的字符串优于该串，因为两串一定仍然同时包括 \(i+k\) 位，所以一定存在优于该串的字符串。
当 \(i>n\) 或 \(j>n\) 时，已经不存在能比较的第二个串，答案即为 \(\min(i,j)\) 开头的字符串。
代码实现
int i=1,j=2,k;
while(i<=n&&j<=n){
k=0;
while(k<n){
if(c[i+k]!=c[j+k]) break;
else k++;
}
if(k==n){
break;
}
if(c[i+k]>c[j+k]){
i+=k+1;
if(i==j) i++;
}else{
j+=k+1;
if(i==j) j++;
}
}