字符串的循環(huán)同構(gòu)：
設(shè)S=bcad，且S’是S的循環(huán)同構(gòu)的串。S’可以是bcad或者cadb,adbc,dbca。而且最小表示的S’是adbc。
對(duì)于字符串循環(huán)同構(gòu)的最小表示法，其問(wèn)題實(shí)質(zhì)是求S串的一個(gè)位置，從這個(gè)位置開(kāi)始循環(huán)輸出S，得到的S’字典序最小。
顯然兩個(gè)字符串循環(huán)同構(gòu)的充分必要條件是這兩個(gè)字符串的最小表示法相等。
字符串循環(huán)同構(gòu)可以看這篇論文：點(diǎn)這里～

下面給出求最小表示法的模板:
函數(shù)返回一個(gè)位置，從這個(gè)位置開(kāi)始循環(huán)輸出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);
}

同理，求最大表示法只是把大于等于號(hào)的內(nèi)容改一下

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);
}