当前位置: 代码迷 >> 综合 >> Circular Sequence, UVa1584
  详细解决方案

Circular Sequence, UVa1584

热度:87   发布时间:2023-12-08 07:15:45.0

Q:

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

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

Code

#include <stdio.h>
#include <string.h>
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()
{char s[101];scanf("%s", s);int n = strlen(s);int ans = 0;for(int i = 1; i < n; i++)//enumerate allif(less(s, i, ans)) ans = i;for(int i = 0; i < n; i++)putchar(s[(ans + i) % n]);return 0;
}

 

 

  相关解决方案