字符串最大最小表示法

对于一个字符串，比如:00ab

它的变形有四种: 00ab ,0ab0,ab00,b00a

那么找到其中字典序最小的一个用的算法就是这个

该模板同时支持最小表示法与最大表示法，由函数的 flag 参数控制。

时间复杂度为 $O(n)$ 双指针，优于朴素枚举所有循环移位再两两比较的 $O(n^2)$ 做法。

代码:

//返回最大最小表示法的第一个字母的位置
int min_max_express(string s,bool flag)//参数为 true 时求最小表示法，为 false 时求最大表示法
{
    int i=0,j=1,k=0;
    int len=s.length();
    while(i<len&&j<len&&k<len)
    {
        int t=s[(j+k)%len]-s[(i+k)%len];
        //二者相等，后移
        if(t==0) k++;
        else
        {
            if(flag)
            {
                if(t>0) j+=k+1;
                else i+=k+1;
            }
            else
            {
                if(t>0) i+=k+1;
                else j+=k+1;
            }
            if(i==j) j++;
            k=0;
        }
    }
    return min(i,j);
}