SRM516 Div1 Easy(250), Div2 Medium(500) NetworkXOneTimePad

NetworkXOneTimePad

鍵の候補は、cipher[0]^plain[0], cipher[0]^plain[1], cipher[0]^plain[2], ……。平文が全て異なるという問題の制約から、この鍵の候補も全て異なる。このなかで全ての暗号文に平文が存在するものを数える。

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long tolong( string t )
{
    int n = (int)t.size();
    long long r = 0;
    for ( int i=0; i<n; i++ )
        if ( t[i]!='0' )
            r |= 1ll<<(n-i-1);
    return r;
}

class NetworkXOneTimePad{public:
int crack( vector <string> plaintexts, vector <string> ciphertexts )
{
    int pn = (int)plaintexts.size();
    int cn = (int)ciphertexts.size();

    vector<long long> plain(pn);
    for ( int i=0; i<pn; i++ )
        plain[i] = tolong(plaintexts[i]);
    vector<long long> cipher(cn);
    for ( int i=0; i<cn; i++ )
        cipher[i] = tolong(ciphertexts[i]);

    int ans = 0;

    for ( int i=0; i<pn; i++ )
    {
        long long key = plain[i]^cipher[0];
        
        bool f = true;
        for ( int j=0; j<cn; j++ )
            if ( find(plain.begin(),plain.end(),cipher[j]^key) == plain.end() )
                f = false;
        if ( f )
            ans++;
    }

    return ans;
}};