def compress_lzw(string, d_size):
    """Apply the LZW Compression algorithm"""

    d = {chr(i): i for i in range(d_size)}
    s = ""
    result = []
    for c in string:
        c_next = c+s
        if c_next in d:
            s = c_next
        else:
            result.append(d[s])
            d[c_next] = d_size
            d_size += 1
            s = c

    if s:
        result.append(d[s])

    return result


def compress(string, dict_size=256):
    """
    LZW Compression Algorithm
    - input -> string (optional dict_size with default value 256)
    - output -> dictionary with the following params:
        - compressed_string,
        - output_dict(codes: indices),
        - compression_ratio
    """

    result = compress_lzw(string, dict_size)

    compressed_string = "".join([chr(i) for i in result])
    output_dict = {chr(i): i for i in result}
    compression_ratio = len(string) / len(compressed_string)

    return {
        'Output string': compressed_string,
        'Output dictionary': output_dict,
        'Compression rate': compression_ratio
    }


string = input()

compressed_string = compress(string)
print(compressed_string)