博客

问题描述

长度为n的环状串有n种表示法，分别为从某 个位置开始顺时针得到。例如，图3-4的环状串 有10种表示：

CGAGTCAGCT，GAGTCAGCTC，AGTCAGCTCG等。在这些表示法中，字典序最小的称 为”最小表示”。

输入一个长度为n（n≤100）的环状DNA串（只包含A、C、G、T这4种字符）的一种表示法，你的任务是输出该环状串的最小表示。例如，CTCC的最小表示是 CCCT，CGAGTCAGCT的最小表示为AGCTCGAGTC。

样例输入

2
CGAGTCAGCT
CTCC

样例输出

AGCTCGAGTC
CCCT

解题思路：使用C++的string类可以方便解决问题。找到最小的字母，然后截取字符串

AC的C++程序：

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int main()
{
	int t;
	string s,ans;
	scanf("%d",&t);
	while(t--){
		cin>>s;
		ans=s;
		int len=s.length();
		s+=s;
		char c=s[0];
		for(int i=1;i<len;i++)
		  if(c>s[i])
		    c=s[i];
		for(int i=0;i<len;i++)
			if(s[i]==c){
			  string temp=s.substr(i,len);
			  if(temp<ans)
			    ans=temp;
			}
		cout<<ans<<endl;
	}
	return 0;
 }