环状序列

￡神魔★判官ぃ 2022-05-28 03:49 202阅读 0赞

#### 前言 ####

没什么好说的了，哈哈，现在快凌晨一点了，为了晚上睡觉不梦见做题，把这个问题还是解决了

#### 环状序列问题描述 ####

长度为n的环状串有n种表示法，分别为某个位置开始顺时针得到。CGAGTCAGCT,GAGTCAGCTC,AGTCAGCTCG等。在这些表示法中，字典序最小的称为“最小表示”。输入一个长度为n(n<=100)的环状DNA串（只包含A、C、G、T这4种字符）的一种表示法，你的任务是输出该环状串的最小表示。例如，CTCC的最小表示是CCCT,CGAGTCAGCT的最小表示为AGCTCGAGTC。  
样例输入：

2  
CGAGTCAGCT  
CTCC

样例输出：

AGCTCGAGTC  
CCCT

描述了很多，其实就是一个字典排序，想想我们的英语字典，apple是不是排在bat前面的？主要就是a比b小，另外apple是不是排在append后面的，因为e比l小。

#### 算法思路 ####

仔细想想这个排序和我们普通的数字大小排序是及其类似的，例如输入rat这个单词，我们首先假设rat最小，然后让atr，tra依次和他进行比较，发现atr最小，就把最小的换成atr这样接着比较（和冒泡排序找最大者不是一模一样吗？）

#### 代码实现 ####

#include<stdio.h>
    #include<string.h>
    #define MAX 105
    int main() {
        char s[MAX];
        int length;
        int small = 0;
        scanf("%s", s);
        length = strlen(s);
        for(int i=1; i<length; i++) {
            if(smaller(s, i, small))
                small = i;
        }
        for(int i=0; i<length; i++) {
            putchar(s[(i+small)%length]);
        }
        return 0;
    }
    
    int smaller(char* s, int current, int small) {
        int length = strlen(s);
        for(int i=0; i<length; i++) {
            if(s[(current+i)%length] != s[(small+i)%length])
                return s[(current+i)%length] < s[(small+i)%length];
        }
        return 0;
    }