《算法竞赛进阶指南》0x15 字符串的最小表示

字符串S从任意位置开始扫描，到了结尾之后从头开始扫描，一共有n个串，他们彼此循环同构，为了求出串S的字典序最小的同构串，可以通过下面的线性时间复杂度的算法得到。

代码如下：

#include<bits/stdc++.h>
using namespace std;
char s[100];
int main(){
    cin>>s+1;
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)s[i+n]=s[i];//循环变成线性 
    int i=1,j=2,k;
    while(i<=n && j<=n){//B[j]与B[i]比较 
        for(k=0;k<n && s[i+k]==s[j+k];k++);
        if(k==n)break; 
        if(s[i+k]>s[j+k]){
            i=i+k+1;
            if(i==j)i++;
        }else{
            j=j+k+1;//跳过不可能为最小串的位置
            if(i==j)j++; 
        }
    }
    int pos=min(i,j);//最小表示的起点
    for(int i=0;i<n;i++)cout<<s[i+pos];
    cout<<endl; 
}