环状序列

长度为n的环状串有n种表示方法，分别为从某个位置开始顺时针得到，在这些排列中字典顺序最小的称“最小表示”。

如CTCC的最小表示为CCCT，CGAGTCAGCT的最小表示为AGCTCGAGTC。

提示：对于两个字符串，从第一的字符开始比较，当某一个位置的字符不同时，该位置字符较小的串，字典序小，如果一个字符串没有更多的字符，但是另一个字符串还没结束，则较短的字符串的字典序较小。

实现：

#include
   
    #include
    
     #define MAX 101int less(char *s, int p, int q)// 比较两个 序列的字典序	{		int n = strlen(s);		for(int i = 0; i < n; i++ ){			if(s[(p+i)%n] != s[(q+i)%n])//意味着元素相同时候继续 直到有不同的元素为止				return s[(p+i)%n] < s[(q+i)%n];//不同时直接返回 大小关系			}					return 0;//到这一步 说明这两个序列 元素一样	} 	int main()	{		char s[MAX];		scanf("%s",&s);		int n = strlen(s);		int ans = 0;				for(int i = 1; i < n; i++ ){			if(less(s, i, ans) == 1)				ans = i;//如果 以第i个位置开始的序列的 字典序 小于从ans位置开始的字典序		}                       //那么 更新 ans 位置为 i				for(int i = 0; i < n; i++ ){			printf("%c",s[(ans+i)%n]);  //  (ans+n-1)%n <-> ans-1(ans前一个) || n-1(ans = 0时) 		}						return 0;	}

思路 : 从输入的第一个字符位置开始(记为ans = 0)为一个序列, 然后记从第二个字符开始为一个序列，每个序列的第一个元素开始按照字典序比较，直到出现第一个不同的元素为止，如果新的序列字典序小于 ans（初始为0）开始的字典序,那么更新 ans为当前序列的初始位置，依次进行直到所有元素比较完。

转载地址：http://taimi.baihongyu.com/

你可能感兴趣的文章