1056:IMMEDIATE DECODABILITY

keyword

prefix　C++

概要

文字列が幾つか与えられたときどの文字列も他の文字列のprefixになっていないかどうか判定する問題。入力のサイズに関する記述が見当たらなかったので愚直に実装してみるとAC。計算量はO(文字列の個数^2 * 文字列の長さ)位だからまだ工夫の余地はあるはず。

int main(){
    string str;
    int i, j, cnt=1, n;
    vector<string> ws;
    while(cin>>str){
        if(str!="9") ws.PB(str);
        else{
            n = SZ(ws);
            REP(i,n)REP(j,n)if(i!=j){
                if(ws[i].length() > ws[j].length() && ws[i].substr(0,ws[j].length()) == ws[j]) goto end;
            }
            end:;
            if(i==n && j==n){
                printf("Set %d is immediately decodable\n", cnt++);
            }
            else{
                printf("Set %d is not immediately decodable\n", cnt++);
            }
            ws.clear();
        }
    }

    return 0;
}