PAT 1084 壞鍵盤：找出確實磨損的按鍵

題目大意

給定原始字符串與實際輸出字符串，找出必定磨損的按鍵。字符包含 A-Z（大小寫不敏感）、0-9、下劃線。輸出順序按原字符串首次發現順序，英文大寫，不重複。

核心邏輯

遍歷原字符串，若某字符在實際輸出中完全找不到，則該按鍵磨損。用集合去重，保持檢測順序輸出。

C++ 簡潔實現

#include <cstdio>
#include <cstring>
#include <set>
#include <cctype>
using namespace std;

int main() {
    char s[100], t[100];
    scanf("%s%s", s, t);
    set seen;
    for (int i = 0; s[i]; ++i) {
        if (!strchr(t, s[i]) && seen.insert(toupper(s[i])).second)
            putchar(toupper(s[i]));
    }
    return 0;
}

樣例解析

原串：7_This_is_a_test
實際：_hs_s_a_es
缺失字符：7, T, I → 輸出 7TI

關鍵點

• strchr 判斷字符是否存在
• set 去重並保證首次檢測順序
• toupper 統一大寫輸出
• 題目保證至少一個磨損按鍵

複雜度

O(|S| × |T|) ≤ 6400，極快。也可預處理 T 進布爾數組優化至 O(|S|+|T|)。