用 Haskell 求解 ACM 竞赛题（9）：环状序列（Circular Sequence, ACM/ ICPC Seoul 2004, UVa1584）

问题：
环状序列（Circular Sequence, ACM/ ICPC Seoul 2004, UVa1584） 环状串长度 为 n 的环状串 有 n 种 表示 法， 分别为从某个位置开始顺时针得到。 例如， 图 3- 4 的环状串有 10 种表示： CGAGTCAGCT， GAGTCAGCTC， AGTCAGCTCG 等。 在这些表示法 中， 字典序最小的称为" 最小表示"。 输入一个长度为 n（ n ≤ 100） 的环状DNA串（只包含 A、 C、 G、 T 这 4 种 字符）的一种表示法， 你的任务是输出 该 环状 串 的 最小表示。 例如， CTCC 的最小表示是 CCCT，CGAGTCAGCT 的最小表示 为 AGCTCGAGTC。

C 语言代码：

#include <stdio.h> 
#include <string.h> 
#define maxn 105 //环状 串 s 的 表示 法 p 是否 比 表示 法 q 的 字典 序 小 
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 T; char s[ maxn]; scanf("% d", &T); while( T--) { scanf("% s", s); int ans = 0; int n = strlen( s); for (int i = 1; i < n; i++) if( less( s, i, ans)) ans = i; for( int i = 0; i < n; i++) putchar( s[( i+ ans)% n]); putchar('\ n'); } return 0; 
}

Haskell 语言代码：

genList' s 0 = []
genList' (x:xs) n = (x:xs) :(genList' (xs ++ [x]) (n-1))
genList s = genList' s (length s)
minstr s = minimum (genList s)