UVa1584环状序列题解

本文主要是介绍UVa1584环状序列题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

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

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

输入输出样例

输入

2
CTCC
CGAGTCAGCT

输出 

CCCT
AGCTCGAGTC

 代码

#include<stdio.h> 
#include<string.h>
#define maxn 105
int less(const char *s,int p,int q){//环串s的表示法p是否比表示法q的字典序小 int n = strlen(s);int i;for(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(){int T;char s[maxn];scanf("%d",&T);while(T--){scanf("%s",s);int ans=0;int n=strlen(s);int i;for(i=1;i<n;i++){if(less(s,i,ans)){//如果表示法i的字典序比表示法ans的字典序小，ans更新为i ans=i;}}for(i=0;i<n;i++){putchar(s[(i+ans)%n]);//环状输出 }putchar('\n');}return 0;
} 

    掌握环状表示法

这篇关于UVa1584环状序列题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---