欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

例题3-6 环状序列(CircularSequence, ACM/ICPC Seoul 2004, UVa1584)

程序员文章站 2022-06-09 16:48:42
...

/*例题3-6 环状序列(CircularSequence, ACM/ICPC Seoul 2004, UVa1584)

长度为n的环状串有n种表示法,分别为从某

个位置开始顺时针得到。例如,图3-4的环状串例题3-6 环状序列(CircularSequence, ACM/ICPC Seoul 2004, UVa1584)

有10种表示:

CGAGTCAGCT,GAGTCAGCTC,AGTCAGCTCG等。

在这些表示法中,字典序最小的称为"最小表示"。

输入一个长度为n(n≤100)的环状DNA串(只包含A、C、G、T这4种字符)的一种表

示法,你的任务是输出该环状串的最小表示。例如,CTCC的最小表示是

CCCT,CGAGTCAGCT的最小表示为AGCTCGAGTC。

【分析】

本题出现了一个新概念:字典序。所谓字典序,就是字符串在字典中的顺序。一般地,

对于两个字符串,从第一个字符开始比较,当某一个位置的字符不同时,该位置字符较小的

串,字典序较小(例如,abc比bcd小);如果其中一个字符串已经没有更多字符,但另一个

字符串还没结束,则较短的字符串的字典序较小(例如,hi比history小)。字典序的概念可

以推广到任意序列,例如,序列1, 2, 4, 7比1, 2, 5小。

学会了字典序的概念之后,本题就不难解决了:就像"求n个元素中的最小值"一样,

变量ans表示目前为止,字典序最小串在输入串中的起始位置,然后不断更新ans*/

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

相关标签: 序列