読者です 読者をやめる 読者になる 読者になる

SRM 672 Div2 Medium SubstitutionCipher

問題

SRM 672 - TopCoder Wiki

大文字からなる文字列について,ある文字をある文字へと変換する変換テーブルで違う文字列へと変換する. 今,変換後の文字列yと部分的な変換テーブルが与えられる. 元の文字列が分かるならその文字列を,分からないなら空文字列を返す問題

解答

  • yに出現する全ての文字が部分的な変換テーブルに現れるならば,単純に計算可能
  • 例外的な場合として,部分的な変換テーブルのサイズが25の場合,元の変換テーブルが26なので,最後の1つの置き換え方法がわかるので,完全な変換テーブルを用いて計算を行う
class SubstitutionCipher
{
public:
  string decode(string a, string b, string y)
    {
      vector<char> table(256, 1);
      int n = a.size();
      int i;
      vector<bool> used(256, false);
      for(i = 0; i < n; i++){
        table[b[i]] = a[i];
        used[a[i]] = true;
      }
      int count = 0;
      int ai = 0, bi = 0;
      for(i = 'A'; i <= 'Z'; i++){
        if (table[i]==1) {
          bi=i;
          // cout << "bi=" << i << endl;
        }
        if (!used[i]) {
          count++;
          ai = i;
        }
      }
      // cout << "count=" << count
      //      << " ai=" << ai
      //      << " bi=" << bi << endl;
      if (count == 1){
        table[bi] = ai;
      }
      string s="";
      for(i = 0; i < y.size(); i++){
        if (table[y[i]]==1) {
          // cout << "y[" << i << "]=" << y[i] << endl;
          return "";
        }
        s += table[y[i]];
      }
      return s;
    }
};