[C++]環狀序列(CircularSequence,ACM/ICPC Seoul 2004,UVa1584)

Question

例題3-5 環狀序列(CircularSequence,ACM/ICPC Seoul 2004,UVa1584)

　　長度為n的環狀串有n種表示方法，分别為從某個位置開始順時針得到，在這些排列中字典順序最小的稱“最小表示”。 如CTCC的最小表示為CCCT，CGAGTCAGCT的最小表示為AGCTCGAGTC。 提示：對于兩個字元串，從第一的字元開始比較，當某一個位置的字元不同時，該位置字元較小的串，字典序小，如果一個字元串沒有更多的字元，但是另一個字元串還沒結束，則較短的字元串的字典序較小。

Think

【概念】

　　字典序：環狀字典序/全排列字典序(含：環狀字典序)

Code

/*
	例題3-5 環狀序列(CircularSequence,ACM/ICPC Seoul 2004,UVa1584)
*/
#include<iostream>
#include<string.h>
using namespace std;

const int maxn = 105;

//比較環狀串s的兩序列q與p的字典序大小，若q<p，傳回值：1;反之：0
static int Less(char *s, int len, int q, int p){
	int cmp;
	for(int i=0;i<len;i++){
		cmp = s[(q+i)%len] - s[(p+i)%len];
		if(cmp > 0){ //q>p
			return -1;
		} else if(cmp < 0){ //q<p
			return 1;
		}
	}
	return 0;//q == p
}

int main(){
	int n;
	int len,ans;//len:字元串長度;	ans:偏移量
	char str[maxn];
	scanf("%d", &n);
	while(n--){
		scanf("%s", &str);
		len = strlen(str);
		for(int i=0;i<len;i++){
			if(Less(str, len, i, ans) > 0) //如果i序列小，則換i
				ans = i;
		}
//		cout<<"Hi"<<endl;//test
		for(int i=0;i<len;i++){
			//printf("%s", str[(ans+i)%len]);//為何此處會卡住？
            putchar(str[(ans+i)%len]);
		}
	}
	return 0;
}
/*
1
CCTC

CCCT
*/