问题描述：

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

image.png

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

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

字典序

让两串字符串从第一个字符开始比较，当出现不同的字符时，字符较小的那个，字典序也较小（例如：abc 比 bca 小）；如果两串字符串其中一个已经没有更多字符而另一个串还没结束，则短的串字典序小（例如：ap 比 apple 小）。

思路

假设序列CTCC就是字典序最小的那个表示，我们只需要检查CTCC 比起TCCC、CCCT和CCTC哪一个字典序更小，如果有比CTCC更小的，就更新，如果没有就继续检查，直到所有的表示都检查完即可（类比冒泡排序，看看是不是和冒泡的思想相同）。

代码

在VS2017上编译通过

#include<stdio.h>
#include<string.h>
#define maxn 100


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 C;
    scanf("%d", &C);

    while (C--)
    {
        char s[maxn];
        scanf("%s", s);
        int n = strlen(s);
        int ans = 0;  // 默认最小序列就是s[0]开头

        // 让默认序列与其他序列比较 
        for (int i = 1; i < n; i++)
            if (less(s, i, ans)) ans = i;

        // 输出最小序列
        for (int j = 0; j < n; j++)
        {
            putchar(s[(ans + j) % n]);
        }
        putchar(10);
    }
    return 0;
}