UVA 620 Cellular Structure：字符串模式識別

問題描述

微生物細胞鏈由 A、B 兩類細胞組成。健康生物的生長遵循三種規則：

1. 簡單階段：空鏈 → "A"
2. 完全生長階段：在右側添加 "AB"
3. 誘變階段：在左側加 'B'，右側加 'A'（即包裹 "BOA"）

給定一條細胞鏈，判斷其處於哪個階段（優先級：SIMPLE > FULLY-GROWN > MUTAGENIC > MUTANT）。

解題思路

觀察生長規則：每次操作增加的長度為 1 或 2。從最終字符串反推：

• 長度為 1 → 必為 "A" → SIMPLE。
• 長度為偶數 → 無法由規則產生 → MUTANT。
• 長度為奇數（≥3）：從兩端向中間檢查。若右端為 'B'，則必須配對左側 'A'（FULLY-GROWN 規則），剔除 "AB"；若右端為 'A'，則必須配對左端 'B'（MUTAGENIC 規則），剔除 "BA"。若過程中不匹配 → MUTANT。最終剔除至長度 1 且為 'A'，則根據最後匹配的規則決定階段。

代碼實現 (C++)

#include 
using namespace std;
int main() {
    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        int len = s.length();
        if (len == 1) { cout << "SIMPLE\n"; continue; }
        if (len % 2 == 0) { cout << "MUTANT\n"; continue; }
        int l = 0, r = len - 1;
        int lastRule = 0; // 1=SIMPLE, 2=FULLY-GROWN, 3=MUTAGENIC
        bool ok = true;
        while (l < r) {
            if (s[r] == 'B') { // 可能是 FULLY-GROWN 添加的 AB
                if (s[r-1] != 'A') { ok = false; break; }
                lastRule = 2;
                r -= 2;
            } else { // s[r] == 'A'，可能是 MUTAGENIC 添加的 BA
                if (s[l] != 'B') { ok = false; break; }
                lastRule = 3;
                ++l; --r;
            }
        }
        if (!ok || l != r || s[l] != 'A') cout << "MUTANT\n";
        else if (lastRule == 2) cout << "FULLY-GROWN\n";
        else if (lastRule == 3) cout << "MUTAGENIC\n";
        else cout << "MUTANT\n";
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n) 每測試用例，n 為字符串長度。
• 空間複雜度：O(1)。

總結

本題通過逆向模擬生長過程，利用字符串兩端字符特徵快速判斷。注意優先級規則：若同時滿足多個階段，輸出優先級最高者（SIMPLE > FULLY-GROWN > MUTAGENIC）。