字符串最小表示

字符串最小表示是指一个给定一个字符串，从特定的为止开始比如说abc可以使bca也可以是cab在这些表示中间，abc是字典序最小的，则abc就是这个字符串的最小表示。字符串最小表示的暴力方法很容易想，就是枚举每一个位置的字符为起始字符，分别比较字典序大小。而我们今天要讨论的是一个O(n)的算法，在线性时间内找到一个字符串的最小表示比如说一个字符串bacad我们一样去找字符串的初始位置，只是不再去全部枚举完所有的字符，比如说，我们知道b>a那么第一个位置肯定不是字符串最小表示的位置，而在两个a的地方，我们需要往下比较，因为c<d所以，第二个a也不是最小表示的位置，以此类推，最后可以确定一个最小表示的开始位置

int minr(char *s)
{
    int i=0,j=1,k=0;
    int l=strlen(s);
    while(i<l&&j<l&&k<l)
    {
        if(s[(i+k)%l]==s[(j+k)%l])
        k++;
        else
        {
            if(s[(i+k)%l]>s[(j+k)%l])
            {
                i+=(k+1);
                if(i==j)
                i++;
            }
            else
            {
                j+=(k+1);
                if(i==j)
                j++;
            }
            k=0;
        }
    }
    return min(i,j);
}