import numpy as np


def lz_decode(codeword, last_symbol_code):
    """Lempel-Ziv-Decoder

    Args:
        codeword (str): String in {0,1}*

        last_symbol_code (dict): Dictionary encoding which code
            corresponds to which last symbol, e.g. {'00': 'a', '01':
            'b', '10': 'c'}

    Returns:
        decoded (str): Decoded message

    """
    # Initialize encoder's dictionary that will be reconstructed
    # during decoding
    dictionary = ['']

    # Compute number of bits needed to encode last symbols
    k = int(np.ceil(np.log2(len(last_symbol_code))))

    # Treat the first k bits specially
    codephrase = codeword[:k]
    decoded = last_symbol_code[codephrase]
    dictionary.append(decoded)

    # Initialize counters
    pos = k  # number of bits that have been decoded
    n = 1
    m = 0

    # Decoding loop
    while len(codeword[pos:]) > 0:
        if len(codeword[pos:]) >= n+k:
            codephrase = codeword[pos: pos + n + k]
            x = int(codephrase[:n], 2)  # convert string in {0,1}* to int
            y = codephrase[n:n+k]
            new_phrase = dictionary[x] + last_symbol_code[y]
        elif len(codeword[pos:]) == n:
            codephrase = codeword[pos:]
            x = int(codephrase[:n], 2)
            y = ''
            new_phrase = dictionary[x]
        pos += n+k
        decoded += new_phrase
        dictionary.append(new_phrase)
        m += 1
        if m == 2**(n-1):
            n += 1
            m = 0

    return decoded