UVa 1584 Circular Sequence 題解：環形串最小字典序 (暴力 + 模擬)

題目大意

給定環形 DNA 序列 (字符集 {A,C,G,T})，長度 L (2~100)。從任意位置起始順時針讀取可得 L 個線性串。求**字典序最小**的線性串並輸出。

例：CGAGTCAGCT → 最小為 AGCTCGAGTC。

算法選擇：直接模擬 (L ≤ 100 足夠)

雖有 O(L) 的 Booth 算法 / 最小表示法，但 L ≤ 100 且測試用例少，**暴力模擬 O(L²) 完全足夠**，代碼簡短、不易出錯。

核心邏輯

1. 讀入串 s，長度 L。
2. ans = s (初始候選)。
3. 循環 L-1 次：每次將 s **循環右移 1 位** (最後一字符移到最前)。
4. 比較 s 與 ans 字典序，若 s < ans 則更新 ans = s。
5. 輸出 ans。

完整 C++ 代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXL = 150;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        char s[MAXL], ans[MAXL];
        scanf("%s", s);
        int L = strlen(s);
        strcpy(ans, s);
        for (int i = 0; i < L; ++i) {
            // 循環右移 1 位：最後字符移到最前
            char last = s[L-1];
            for (int j = L-1; j >= 1; --j) s[j] = s[j-1];
            s[0] = last;
            if (strcmp(s, ans) < 0) strcpy(ans, s);
        }
        printf("%s\n", ans);
    }
    return 0;
}

關鍵實現細節

1. 循環右移**：從後向前覆蓋 s[j] = s[j-1]，最後 s[0] = last。**不能用 strcpy(s+1, s)** — 源與目標重疊，行為未定義。
2. 字典序比較**：直接用 strcmp，返回 <0 表示前者較小。
3. 複製更新**：strcpy(ans, s) 更新最佳候選。
4. 循環次數**：L 次 (含原始串)，或 L-1 次移動 + 原始串。

複雜度分析

• 時間：O(T × L²)。L≤100，T 通常 ≤ 100，極快 (10⁶ 量級操作)。
• 空間：O(L)。

進階：O(L) 最小表示法 (Booth 算法)

若 L 達 10⁵+，需線性算法：

int min_cyclic_string(const char* s, int n) {
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        char a = s[(i+k)%n], b = s[(j+k)%n];
        if (a == b) ++k;
        else {
            if (a > b) i = i + k + 1;
            else j = j + k + 1;
            if (i == j) ++i;
            k = 0;
        }
    }
    return min(i, j); // 返回最小表示起始索引
}

但本題 **暴力模擬更具性價比** — 代碼量 1/5，無邊界條件 Bug 風險，AC 概率更高。

避坑指南

1. 輸入可能包含換行/空格**：用 scanf("%s") 自動跳過空白。
2. 字符集僅 {A,C,G,T}**：無需處理其他字符。
3. 多測試用例**：外層循環 T 次。
4. 輸出每行一個答案**：無額外空格/空行。

結語

UVa 1584 是「暴力模擬戰勝理論優化」的典型案例。在數據範圍極小 (L≤100) 時，**代碼簡潔性、正確性、編寫速度**遠比理論時間複雜度重要。直接模擬循環移位 + strcmp 比較，幾行代碼解決問題，是競賽與工程中「知己知彼、因地制宜」的最佳體現。理解 Booth 算法原理固然重要，但會選擇合適工具解決具體問題，才是核心能力。