原題及翻譯

Some DNA sequences exist in circular forms as in the following figure, which shows a circular sequence “CGAGTCAGCT”, that is, the last symbol “T” in “CGAGTCAGCT” is connected to the first symbol “C”.
如下圖所示，一些DNA序列以圓形存在，顯示了一個圓形序列“cgagtacgt”，即“cgagtacgt”中的最后一個符號“t”與第一個符號“c”相連。

We always read a circular sequence in the clockwise direction.
我們通常在順時針方向讀取一個圓形序列。
Since it is not easy to store a circular sequence in a com- puter as it is, we decided to store it as a linear sequence.
由于在計算機中存儲循環序列并不容易，因此我們決定將其存儲為線性序列。
However, there can be many linear sequences that are ob- tained from a circular sequence by cutting any place of the circular sequence.
然而，通過切割圓形序列的任何位置，可以從圓形序列中獲得許多線性序列。
Hence, we also decided to store the linear sequence that is lexicographically smallest among all linear sequences that can be obtained from a circular sequence.
因此，我們還決定存儲線性序列，它在所有可以從循環序列中獲得的線性序列中在詞典上是最小的。
Your task is to find the lexicographically smallest sequence from a given circular sequence.
您的任務是從給定的循環序列中查找詞典上最小的序列。
For the example in the figure,
對于圖中的例，
the lexicographically smallest sequence is “AGCTCGAGTC”.
詞典最小的序列是“agctcgagtc”。
If there are two or more linear sequences that are lexicographically smallest, you are to find any one of them (in fact, they are the same).
如果有兩個或兩個以上的線性序列在詞典上是最小的，那么您可以找到它們中的任何一個（事實上，它們是相同的）。

Input

輸入
The input consists of T test cases.
輸入由T測試用例組成。
The number of test cases T is given on the first line of the input file.
一行給出測試用例數t。
Each test case takes one line containing a circular sequence that is written as an arbitrary linear sequence.
在輸入文件的第每個測試用例采用一行，其中包含一個循環序列，該循環序列被寫成一個任意的線性序列。
Since the circular sequences are DNA sequences, only four symbols, ‘A’, ‘C’, ‘G’ and ‘T’, are allowed.
由于圓形序列是DNA序列，因此只允許使用“A”、“C”、“G”和“T”四個符號。
Each sequence has length at least 2 and at most 100.
每個序列的長度至少為2，最多為100。

Output

輸出
Print exactly one line for each test case.
每個測試用例只打印一行。
The line is to contain the lexicographically smallest sequence for the test case.
該行包含測試用例的詞典最小序列。

Sample Input

2
CGAGTCAGCT CTCC

Sample Output

AGCTCGAGTC CCCT

題目理解

長度為n的環狀序列有n種表示方法，分別為從某個位置開始順時針得到。其中，字典序最小的稱為“最小表示”。
輸入一個長度為n（n<=100）的環狀DNA串（只包含A,C,G,T這4種字符）的一種表示法，你的任務是輸出該環狀串的最小表示。

思路

所謂的字典序，就是字符串在字典中的順序。

一般地，對于兩個字符串，從第一個字符開始比較，當某一個位置的字符不同時，該位置字符較小的串，字典序較小；如果其中一個字符串已經沒有更多字符，但另一個字符串還沒結束，則較短的字符串的字典序較小。

字典序的可以推廣到任意序列。

代碼

#include <stdio.h> #include <string.h> #define maxn 105 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; }

總結

以上是生活随笔為你收集整理的Circular Sequence UVA - 1584的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。