e394 - 許蓋功問題
題目描述
題目要求判斷給定的字串是否包含預先定義的“許蓋功字元”。這些字元以長度為 1、2 或 3 的字串形式存在。如果字串中包含任何一個“許蓋功字元”，則輸出 "Yes"，否則輸出 "No"。
解題思路
此題的核心是判斷輸入字串是否包含預定義的字元集合中的任何字串。程式使用一個 map (相當於 Hash Table) 來儲存所有“許蓋功字元”，然後遍歷輸入字串，檢查長度為 1、2 或 3 的子字串是否存在於 map 中。如果找到任何匹配的子字串，則立即判斷字串包含“許蓋功字元”，並輸出 "Yes"。如果遍歷完整個字串都沒有找到匹配的子字串，則輸出 "No"。
複雜度分析
- 時間複雜度: O(n * k)，其中 n 是輸入字串的長度，k 是最長“許蓋功字元”的長度 (在本例中為 3)。因為需要遍歷字串，並在每次迭代中檢查長度最多為 3 的子字串。
- 空間複雜度: O(m)，其中 m 是“許蓋功字元”的數量。這是因為
map用於儲存所有“許蓋功字元”。
程式碼
#include <iostream>
#include <map>
using namespace std;
map<string, int> m = {{"﹏", 1}, {"兝", 1}, {"α", 1}, {"么", 1}, {"功", 1}, {"吒", 1}, {"吭", 1}, {"沔", 1}, {"坼", 1}, {"歿", 1}, {"俞", 1}, {"枯", 1}, {"苒", 1}, {"娉", 1}, {"珮", 1},{"豹", 1}, {"崤", 1}, {"淚", 1}, {"許", 1}, {"廄", 1}, {"琵", 1}, {"跚", 1}, {"愧", 1}, {"稞", 1}, {"鈾", 1}, {"暝", 1}, {"蓋", 1}, {"墦", 1}, {"穀", 1}, {"閱", 1},{"璞", 1}, {"餐", 1}, {"縷", 1}, {"擺", 1}, {"黠", 1}, {"孀", 1}, {"髏", 1}, {"躡", 1}, {"尐", 1}, {"佢", 1}, {"汻", 1}, {"岤", 1}, {"狖", 1}, {"垥", 1}, {"柦", 1},{"胐", 1}, {"娖", 1}, {"涂", 1}, {"罡", 1}, {"偅", 1}, {"惝", 1}, {"牾", 1}, {"莍", 1}, {"傜", 1}, {"揊", 1}, {"焮", 1}, {"茻", 1}, {"鄃", 1}, {"幋", 1}, {"滜", 1},{"綅", 1}, {"赨", 1}, {"塿", 1}, {"槙", 1}, {"箤", 1}, {"踊", 1}, {"嫹", 1}, {"潿", 1}, {"蔌", 1}, {"醆", 1}, {"嬞", 1}, {"獦", 1}, {"螏", 1}, {"餤", 1}, {"燡", 1},{"螰", 1}, {"駹", 1}, {"礒", 1}, {"鎪", 1}, {"瀙", 1}, {"酀", 1}, {"瀵", 1}, {"騱", 1}, {"酅", 1}, {"贕", 1}, {"鱋", 1}, {"鱭", 1}};
int main(){
string b;
while(getline(cin,b)){
int ac=1;
for(int i=0;i<b.length()&∾++i){
string a;
a+=b[i];
if(m.find(a)!=m.end())ac=0;
a+=b[i+1];
if(m.find(a)!=m.end())ac=0;
a+=b[i+2];
if(m.find(a)!=m.end())ac=0;
}
if(ac==0)cout << "Yes\n";
else cout << "No\n";
}
}