字符串的最小表示法

字符串的循环同构：
设S=bcad，且S’是S的循环同构的串。S’可以是bcad或者cadb,adbc,dbca。而且最小表示的S’是adbc。
对于字符串循环同构的最小表示法，其问题实质是求S串的一个位置，从这个位置开始循环输出S，得到的S’字典序最小。
显然两个字符串循环同构的充分必要条件是这两个字符串的最小表示法相等。
字符串循环同构可以看这篇论文：点这里～

下面给出求最小表示法的模板:
函数返回一个位置，从这个位置开始循环输出S，得到的S’字典序最小。

int getMin(char *str)
{
    int i=0,j=1,k=0;
    int slen=strlen(str);
    while(i<slen&&j<slen&&k<slen)
    {
        int tmp=str[(i+k)%slen]-str[(j+k)%slen];
        if(tmp==0) k++;
        else
        {
            if(tmp>0) i=i+k+1;
            else j=j+k+1;
            if(j==i) j++;
            k=0;
        }
    }
    return min(i,j);
}

同理，求最大表示法只是把大于等于号的内容改一下

int getMax(char *str)
{
    int i=0,j=1,k=0;
    int slen=strlen(str);
    while(i<slen&&j<slen&&k<slen)
    {
        int tmp=str[(i+k)%slen]-str[(j+k)%slen];
        if(tmp==0) k++;
        else
        {
            if(tmp>0) j=j+k+1;
            else i=i+k+1;
            if(i==j) j++;
            k=0;
        }
    }
    return min(i,j);
}