第8回オフラインリアルタイムどう書くの参考問題の回答例。C++で。

#include <iostream>
#include <sstream>
#include <string>

static const std::string NIBBLES[] =
{
    "0000", "1000", "0100", "1100", "0010", "1010", "0110", "1110",
    "0001", "1001", "0101", "1101", "0011", "1011", "0111", "1111"
};

static const std::string HEXES = "0123456789abcdef";

std::string solve(const std::string& input)
{
    std::string bits;
    for(std::string::const_iterator i = input.begin(); i != input.end(); ++i)
    {
        bits += NIBBLES[HEXES.find(*i)];
    }

    std::string::size_type pos = 0;
    std::string            result;
    for(;;)
    {
        if     (bits.size() <= pos)               { pos = std::string::npos; break; }
        else if(bits.substr(pos, 3) == "000"    ) { result += 't'; pos += 3; }
        else if(bits.substr(pos, 4) == "0010"   ) { result += 's'; pos += 4; }
        else if(bits.substr(pos, 4) == "0011"   ) { result += 'n'; pos += 4; }
        else if(bits.substr(pos, 4) == "0100"   ) { result += 'i'; pos += 4; }
        else if(bits.substr(pos, 5) == "01010"  ) { result += 'd'; pos += 5; }
        else if(bits.substr(pos, 7) == "0101101") { result += 'c'; pos += 7; }
        else if(bits.substr(pos, 6) == "010111" ) { result += 'l'; pos += 6; }
        else if(bits.substr(pos, 4) == "0110"   ) { result += 'o'; pos += 4; }
        else if(bits.substr(pos, 4) == "0111"   ) { result += 'a'; pos += 4; }
        else if(bits.substr(pos, 2) == "10"     ) { result += 'e'; pos += 2; }
        else if(bits.substr(pos, 4) == "1100"   ) { result += 'r'; pos += 4; }
        else if(bits.substr(pos, 4) == "1101"   ) { result += 'h'; pos += 4; }
        else if(bits.substr(pos, 3) == "111"    ) { pos += 3; break; }
        else                                      { pos = std::string::npos; break; }
    }

    if(pos != std::string::npos)
    {
        std::ostringstream output;
        output << result << ":" << pos;
        return output.str();
    }
    else
    {
        return "*invalid*";
    }
}

void test(const std::string& input, const std::string& expected)
{
    std::string actual = solve(input);
    std::cout << actual << " => " << (actual == expected ? "o" : "x") << "¥n";
}

int main(int, char* [])
{
    /*0*/ test( "16d9d4fbd", "ethanol:30" );
    /*1*/ test( "df", "e:5" );
    /*2*/ test( "ad7", "c:10" );
    /*3*/ test( "870dcb", "t:6" );
    /*4*/ test( "880f63d", "test:15" );
    /*5*/ test( "a57cbe56", "cat:17" );
    /*6*/ test( "36abef2", "roll:23" );
    /*7*/ test( "ad576cd8", "chant:25" );
    /*8*/ test( "3e2a3db4fb9", "rails:25" );
    /*9*/ test( "51aa3b4c2", "eeeteee:18" );
    /*10*/ test( "ad5f1a07affe", "charset:31" );
    /*11*/ test( "4ab8a86d7afb0f", "slideshare:42" );
    /*12*/ test( "ac4b0b9faef", "doctor:30" );
    /*13*/ test( "cafebabe", "nlh:17" );
    /*14*/ test( "43e7", "sra:15" );
    /*15*/ test( "53e7", "eera:15" );
    /*16*/ test( "86cf", "tera:16" );
    /*17*/ test( "b6cf", "hon:15" );
    /*18*/ test( "0", "*invalid*" );
    /*19*/ test( "c", "*invalid*" );
    /*20*/ test( "d", "*invalid*" );
    /*21*/ test( "e", "*invalid*" );
    /*22*/ test( "babecafe", "*invalid*" );
    /*23*/ test( "8d", "*invalid*" );
    /*24*/ test( "ad", "*invalid*" );
    /*25*/ test( "af", "*invalid*" );
    /*26*/ test( "ab6e0", "*invalid*" );
    /*27*/ test( "a4371", "*invalid*" );
    /*28*/ test( "a4371", "*invalid*" );
    /*29*/ test( "96e3", "*invalid*" );
    /*30*/ test( "0dc71", "*invalid*" );
    /*31*/ test( "2a9f51", "*invalid*" );
    /*32*/ test( "a43fb2", "*invalid*" );
    /*33*/ test( "ab6e75", "*invalid*" );
    /*34*/ test( "a5dcfa", "*invalid*" );
    /*35*/ test( "ca97", "*invalid*" );
    /*36*/ test( "6822dcb", "*invalid*" );

    return 0;
}