环状序列（逐行解析）（保姆式解析）（算法竞赛入门经典二）

长度为n的环状串有n种表示法，分别为某个位置开始顺时针得到。例如，图中的环状串有10种表示：
CGAGTCAGCT,GAGTCAGCTC,AGTCAGCTCG等。在这些表示法中，字典序最小的称为“最小表示”。

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

输入：
在输入文件的第一行 为序列数量。每一个测试用例都需要一行包含一个循环序列，
这个序列被写成一个任意的线性序列。
由于循环序列是DNA串，只有四个符号:A,C,G,T。
每一序列的长度为n(2<=n<=100)。

输出：
每行为串的字典序最小的序列。下面的样例为2个串的序列。

样例输入：
2
CGAGTCAGCT
CTCC

样例输出：
AGCTCGAGTC
CCCT

#include
#include
#define maxn 100


int less(const char* s, int p, int q)//见下注释2
{
    int n = strlen(s);

    for (int i = 0; i < n; i++)
    {
        if (s[(p + i) % n] != s[(q + i) % n])//%n是为了将转了一圈后将那一圈减去，类似13：00就是1：00
            return s[(p + i) % n] < s[(q + i) % n];/*这里p是main里i, q是ans，一旦找到某个字符串i打
头比ans打头字典序更小，返回1，才会把i赋值给ans（见main（））。注意是字典序最小，不是打头
元素最小，所以要用for循环，一个一个往下找，找到不一样的才return*/
。
    }
    return 0; //相等
}

int main()
{
    int C;
    scanf("%d", &C);//输入要判断几个环状序列

    while (C--)//见下注释1
    {
        char s[maxn];//创立数组存储字符串
        scanf("%s", s);//输入要判断的序列
        int n = strlen(s);//计算该序列的长度
        int ans = 0;  // ans是指最小的那个开头的数，默认最小序列就是s[0]开头

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

注释1
这里我曾经想了好久，不理解为什么会用循环，其实后来发现是我理解错了，这里我原来以为输入的是字符串长度，其实是用来判断多个环状序列的

注释2
这里就是整个判断的关键部分，由less这个函数可以直接判断出最小序列

首先我们从一个数进入，例如就是c

然后此时i=1，ans=0,接着进入less函数（注意此时i就是p，ans就是q）。进入第一次循环，此时就判断s[1]是否等于s[0]

这里很明显c

这时s[2]

很明显不成立，则ans值不改变，紧着向下进行

好接下来遇到第二个问题，如果开头相同怎么办？

此时ans=2,i=6,进入函数，结果s[2]==s[6],那么这时候for循环就发挥作用啦，比较第二个数，也就是s[3]和s[7]

结果发现还相等，就再for一次，比较s[4]和s[8]

这里就可以看出s[8]

那么到这其实思路就很清晰啦，%n就是为了让它的数不超过字符串长度（这里就是9），每次判断都是寻找最小的数，如果相同，就再比较下一级，直到找出小的序列，然后改变开头数（ans）。

main函数里的for就是用来判断开头数哪个小，而less函数里的for就是用来判断如果开头数相同，那么就比较下一个数，再比较下一个，直到不相同（ps:如果开头数不同的话其实for循环是没啥用的）