ZOJ 3818 Pretty Poem 解題報告：模擬枚舉 ABABA/ABABCAB 韻律模式

題目大意

給定一行詩句（長度 ≤ 50），去除標點後僅保留字母。判斷是否能分解為 ABABA 或 ABABCAB 兩種韻律模式之一。其中 A、B、C 為非空且互不相同的連續子串。多測試用例，輸出 Yes/No。

核心思路：暴力枚舉長度 + 子串比較

因長度極小 (≤50)，可直接枚舉 A、B、C 的長度邊界，將字符串切分為對應片段逐一比對。

模式一：ABABA → 結構 X Y Z

• 設 |A| = i, |B| = j，則總長 = 3i + 2j；
• 枚舉 i (1..L/3)，j (1..(L-3i)/2)；
• 切分：X=A, Y=B, Z=A 尾部；驗證 X==Y? 不，驗證首尾 A 相等、中間 B 相等、A≠B。

模式二：ABABCAB → 結構 X Y W Z

• |A|=i, |B|=j, |C|=k，總長 = 3i + 2j + k；
• 三重枚舉 i,j,k，切分驗證 A、B、C 互異且位置匹配。

關鍵代碼片段 (C++)

bool checkABABA(const string& s) {
    int L = s.length();
    for (int i = 1; 3*i <= L; ++i) {           // |A|
        for (int j = 1; 3*i + 2*j <= L; ++j) { // |B|
            string A = s.substr(0, i);
            string B = s.substr(i, j);
            if (A == B) continue;
            // 位置: A B A B A
            if (s.substr(i+j, i) != A) continue;
            if (s.substr(2*i+j, j) != B) continue;
            if (s.substr(2*i+2*j) != A) continue;
            return true;
        }
    }
    return false;
}

bool checkABABCAB(const string& s) {
    int L = s.length();
    for (int i = 1; 3*i <= L; ++i) {
        for (int j = 1; 3*i + 2*j < L; ++j) {
            for (int k = 1; 3*i + 2*j + k <= L; ++k) {
                string A = s.substr(0, i);
                string B = s.substr(i, j);
                string C = s.substr(2*i + 2*j, k);
                if (A==B || A==C || B==C) continue;
                if (s.substr(i+j, i) != A) continue;
                if (s.substr(2*i+j, j) != B) continue;
                if (s.substr(2*i+2*j+k) != A) continue;
                if (s.substr(3*i+2*j+k) != B) continue;
                return true;
            }
        }
    }
    return false;
}

預處理：去除標點

string filter(const string& raw) {
    string res;
    for (char c : raw) if (isalpha(c)) res += c;
    return res;
}

複雜度分析

L ≤ 50，三重循環最約 50³/6 ≈ 2萬次，字符串比較 O(L)，總操作 < 10⁶，輕鬆通過 2s 時限。

測試樣例

總結

題目本質是定長字符串的模式匹配，利用長度極小特性，暴力枚舉配合 substr 比對最直觀、不易出錯。關鍵細節：去除標點、A/B/C 非空且互異、邊界條件精確。