1  /*
   2   * Homework #18: http://hvprogrammers.org/homework-18.html
   3   *   by Frank W.
   4   */
   5  
   6  import std.stdio;
   7  
   8  interface Node
   9  {
  10    char decode1(string bits, out string rest);
  11  
  12    final static Node parse(string pre, ref string rest)
  13    {
  14      assert(pre != "");
  15      
  16      switch (pre[0]) {
  17      case '*':
  18        auto left  = Node.parse(pre[1 .. $], rest);
  19        auto right = Node.parse(rest, rest);
  20        return new Internal(left, right);
  21        
  22      default:
  23        rest = pre[1 .. $];
  24        return new Leaf(pre[0]);
  25      }
  26    }
  27  }
  28  
  29  class Internal : Node
  30  {
  31    private Node left;
  32    private Node right;
  33    
  34    this(Node left, Node right)
  35    {
  36      this.left = left;
  37      this.right = right;
  38    }
  39    
  40    char decode1(string bits, out string rest)
  41    {
  42      assert(bits != "");
  43      assert(bits[0] == '0' || bits[0] == '1');
  44      
  45      auto child = (bits[0] == '0' ? left : right);
  46  
  47      bits = bits[1 .. $];
  48      return child.decode1(bits, rest);
  49    }
  50  }
  51  
  52  class Leaf : Node
  53  {
  54    private char value;
  55    
  56    this(char value)
  57    {
  58      this.value = value;
  59    }
  60    
  61    char decode1(string bits, out string rest)
  62    {
  63      rest = bits;
  64      return value;
  65    }
  66  }
  67  
  68  class HuffmanTree
  69  {
  70    private Node root;
  71  
  72    /* Construct a tree from the preorder traversal */
  73    this(string pre)
  74    {
  75      string rest;
  76      root = Node.parse(pre, rest);
  77      assert(rest == "");
  78    }
  79  
  80    /* Decode a string of bits like "110100" */
  81    string decode(string bits)
  82    {
  83      string msg = "";
  84    
  85      while (bits != "") {
  86        string rest;
  87        msg ~= root.decode1(bits, rest);
  88        bits = rest;
  89      }
  90      
  91      return msg;
  92    }
  93  }
  94  
  95  static string trim(string s)
  96  {
  97    if (s == "") return s;
  98    if (s[$-1] != '\n') return s;
  99    return s[0 .. $-1];
 100  }
 101  
 102  void main()
 103  {
 104    string pre;
 105    stdin.readln(pre);
 106    
 107    string bits;
 108    stdin.readln(bits);
 109    
 110    auto tree = new HuffmanTree(trim(pre));
 111    writeln(tree.decode(trim(bits)));
 112  }