SRM480 Easy:InternetSecurity

keyword

C++

概要

サイトのアドレス名、各サイトが含んでいるキーワード、危険ワード、閾値が与えられる。閾値以上の危険ワードを含むサイトは危険であると判断され、そのサイトが含むキーワードは危険ワードに追加される。危険なサイトのアドレスを返す問題。
危険ワードが途中で増えるので何度もループを回す必要がある。ループ回数はアップデートするかどうかのフラグで管理してもよいし、サイトの数だけ回してもよい。

  vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold) {
    set<string> dang;
    int i, j, loop, n=SZ(address);
    string str;
    vector<bool> isDang(n,false);
    vector<string> ret;
    vector<vector<string> > keys(n);
    REP(i,n){
        istringstream ist(keyword[i]);
        while(ist>>str){
            keys[i].PB(str);
        }
    }
    REP(i,SZ(dangerous)) dang.insert(dangerous[i]);
    REP(loop,51){
        REP(i,n)if(!isDang[i]){
            int cnt = 0;
            REP(j,SZ(keys[i])){
                if(dang.find(keys[i][j])!=dang.end()){
                    cnt++;
                }
            }
            if(cnt>=threshold){
                isDang[i] = true;
                REP(j,SZ(keys[i])){
                    dang.insert(keys[i][j]);
                }
            }
        }
    }

    REP(i,n)if(isDang[i])ret.PB(address[i]);

    return ret;

  }