字符串的循環(huán)同構(gòu)：
設(shè)S=bcad贮预，且S’是S的循環(huán)同構(gòu)的串鉴分。S’可以是bcad或者cadb,adbc,dbca糯笙。而且最小表示的S’是adbc妹田。
對于字符串循環(huán)同構(gòu)的最小表示法唬党，其問題實(shí)質(zhì)是求S串的一個位置鹃共，從這個位置開始循環(huán)輸出S，得到的S’字典序最小初嘹。
顯然兩個字符串循環(huán)同構(gòu)的充分必要條件是這兩個字符串的最小表示法相等及汉。
字符串循環(huán)同構(gòu)可以看這篇論文：點(diǎn)這里～
下面給出求最小表示法的模板:
函數(shù)返回一個位置，從這個位置開始循環(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);
}
同理，求最大表示法只是把大于等于號的內(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);
}
