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

╰+攻爆jí腚メ 2024-03-31 13:17 101阅读 0赞

#### 环状序列 ####

![在这里插入图片描述][ed9a24a691054fbaa9884cb2f6737939.png]

长度为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  
![在这里插入图片描述][0db96fe7d2c94ea291c99c0bf6c5db4d.png]

![在这里插入图片描述][de6f49c02a9e4728a64a3d59bd9378c4.png]

#include<stdio.h>
    #include<string.h>
    #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  
> 这里就是整个判断的关键部分，由less这个函数可以直接判断出最小序列**

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

![在这里插入图片描述][a818cad7ef874f1dad2fd3e579ae941d.png]

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

![在这里插入图片描述][d758fc0a9ff341e1b5027326eef7f6e7.png]  
**这里很明显c<g,那么s\[1\]就大于s\[0\],所以判断不成立返回0，接着返回主函数，ans值不变，接着i变为2，再进入函数，此时就是比较s\[2\]和s\[0\]**

![在这里插入图片描述][577dc6901c70431ca191878aaacaea88.png]

**这时s\[2\]<s\[0\],判断成立返回1，则ans值改变，变为2，那么下一次序列就从s\[2\]开头，接着i变为3，就是比较s\[3\]和s\[2\]**

![在这里插入图片描述][604f35c0d0f5410b91a4db47dbbe52d0.png]  
**很明显不成立，则ans值不改变，紧着向下进行**

![在这里插入图片描述][af2d7ad56e094a2598fa3958a449f622.png]  
![在这里插入图片描述][b9060a298e0e40a49845751579b2e54f.png]  
**好接下来遇到第二个问题，如果开头相同怎么办？**

![在这里插入图片描述][06f61416967842afb815708a9fe663cb.png]  
**此时ans=2,i=6,进入函数，结果s\[2\]==s\[6\],那么这时候for循环就发挥作用啦，比较第二个数，也就是s\[3\]和s\[7\]**

![在这里插入图片描述][7042dbb27d774c8ba90f8c9ec14428c6.png]  
**结果发现还相等，就再for一次，比较s\[4\]和s\[8\]**

![在这里插入图片描述][6ee95333ab4a47b5af67a3b91d27142e.png]  
**这里就可以看出s\[8\]<s\[4\]啦，判断成立，返回1，ans的值改变为i，也就是6，那么此时就是从s\[6\]开头啦**

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

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

![在这里插入图片描述][ecec4f1639e64b9ba335e2d41748c6e9.png]

[ed9a24a691054fbaa9884cb2f6737939.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/aed49843bd1b44d8addc15e06ab5e756.png
[0db96fe7d2c94ea291c99c0bf6c5db4d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/ce8437c10c054c0cbb10675e086029e4.png
[de6f49c02a9e4728a64a3d59bd9378c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/b3dcf5e1fe2c45d798fda5c48e0b781e.png
[a818cad7ef874f1dad2fd3e579ae941d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/8d3e893d39004fff869870c933b863a4.png
[d758fc0a9ff341e1b5027326eef7f6e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7229abbc78b04eeb9d9dab451d3c533a.png
[577dc6901c70431ca191878aaacaea88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2b2adb2f4a7b458a9dba895e1b820359.png
[604f35c0d0f5410b91a4db47dbbe52d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/4f856c4977274bc9b4f200e06002c0a6.png
[af2d7ad56e094a2598fa3958a449f622.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6a1dbe46568f44cdbbc012930e8326ab.png
[b9060a298e0e40a49845751579b2e54f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/053189074f5c40999782f9e796fe4425.png
[06f61416967842afb815708a9fe663cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a09f78079230401085b643ce8d33de6b.png
[7042dbb27d774c8ba90f8c9ec14428c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c14907116fce46ae8f0620c5e5f71d36.png
[6ee95333ab4a47b5af67a3b91d27142e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/94092983f8c641108422881df1e5d125.png
[ecec4f1639e64b9ba335e2d41748c6e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/62ee293784644f36bb5f414736606dd9.png