Codeforces 538A Cutting Banner：子串刪除構造 CODEFORCES

題目描述

給定字符串 s（長度 ≤ 100），可刪除一個連續子串，剩餘前後部分拼接。問能否得到 "CODEFORCES"。

解題思路：枚舉分割點

目標串 t = "CODEFORCES"（長 10）。若 s 刪除中間一段後等於 t，則 s 的前綴匹配 t 的前綴，後綴匹配 t 的後綴，且前綴長 + 後綴長 = 10。枚舉 k = 0..10：

• 檢查 s[0..k-1] == t[0..k-1] 且 s[n-10+k..n-1] == t[k..9]。
• 若存在滿足者，答案 YES。

C++ 代碼實現

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s; cin >> s;
    string t = "CODEFORCES";
    int n = s.size(), m = t.size();
    if (n < m) { cout << "NO\n"; return 0; }
    for (int k = 0; k <= m; ++k) {
        bool ok = true;
        for (int i = 0; i < k; ++i)
            if (s[i] != t[i]) { ok = false; break; }
        for (int i = 0; i < m - k; ++i)
            if (s[n - (m - k) + i] != t[k + i]) { ok = false; break; }
        if (ok) { cout << "YES\n"; return 0; }
    }
    cout << "NO\n";
    return 0;
}

複雜度

• 時間：O(n × m) = O(1000)，極快。
• 空間：O(1)。