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

UVa10896 Known Plaintext Attack

問題
http://uva.onlinejudge.org/external/108/10896.html

概要
アルファベットのみがシーザー暗号化された暗号文と、平文の一単語が入力として与えられる。暗号鍵を、平文の一文字を 'a' としたときに暗号化された一文字とするとき、あり得る暗号鍵を全てアルファベット順に出力せよ。

解法
はじめに与えられる平文の単語と一致する長さを持つ暗号文の単語の集合を取得する。その文字列の集合のうち、各文字が対応する平文の単語の文字と比較して、同じ数の分だけずれているならば答えの候補となる。そのずれ+'a'が暗号鍵となるので、それを全て列挙すればよい。

#include <bits/stdc++.h>
using namespace std;

int main() {
  
  int Tc; cin >> Tc;
  cin.ignore();
  while(Tc--) {
    string str; getline(cin, str);
    string word; getline(cin, word); int const N = word.size();
    stringstream ss(str);
    string s;
    
    vector<string> vec;
    while(ss >> s)
      if(N == s.size()) { vec.push_back(s); }
    
    set<char> ans;
    for(int i=0; i<vec.size(); i++) {
      int diff = vec[i][0]-word[0];
      if(diff < 0) diff += 26;
      
      bool ok = true;
      for(int j=0; j<N; j++) {
        int d = vec[i][j] - word[j];
        if(d < 0) { d += 26; }
        if( diff != d) { ok = false; }
      }
      
      if(ok) { ans.insert((char)('a'+diff)); }
    }
    
    for(set<char>::iterator it = ans.begin();
        it!=ans.end(); it++) cout << *it;
    cout << endl;
  }
  
  return 0;
}