def lzw(data,alpha):
  d = {}
  s = data[0]
  data = data[1:]
  ret = []
  code = 0

  print('s\t | c\t | out\t | code\t | str')
  
  for c in alpha:
    d[c] = code
    print('\t | \t | \t | '+str(code)+'\t | '+c)
    code += 1
  for c in data:
    if d.has_key(s+c):
      s = s+c
      print(s+'\t | '+c+'\t | \t | \t | ')
    else:
      ret.append(d[s])
      print(s+'\t | '+c+'\t | '+str(d[s])+'\t | '+str(code)+'\t | '+s+c)
      d[s+c] = code
      code += 1
      s = c
  print(s+'\t | \t | '+str(d[s])+'\t | \t | ')
  ret.append(d[s])
  return ret

def ilzw(data,alpha):
  d = {}
  code = 0
  ret = []
  s = ''
  print('s\t | k\t | out\t | code\t | str')
  for c in alpha:
    d[code] = c
    print('\t | \t | \t | '+str(code)+'\t | '+c)
    code += 1
  for k in data:
    if not d.has_key(k):
      entry = s + s[0]
    else:
      entry = d[k]

    ret.append(entry)
    if s != '':
      d[code] = s+entry[0]
      print(s+'\t | '+str(k)+'\t | '+entry+'\t | '+str(code)+'\t | '+s+entry[0])
      code += 1
    else:
      print(s+'\t | '+str(k)+'\t | '+entry+'\t | \t | ')
    s = entry
  return ''.join(ret)
 
tests = [ '0110011',
          'ABABBABCABABBA',
          'ABBABBA',
          '011011000000101011010110001011010110100100101010111010101010101' ]

# print(lzw('01'))
# print(ilzw(lzw('0110011','01'),'01'))

l=lzw('ABABBABCABBABBA','ABC')
# l=lzw('AAAA','A')
print(l)
print(ilzw(l,'ABC'))

# print(lzw('011011000000101011010110001011010110100100101010111010101010101','01'))
# print(ilzw(lzw('011011000000101011010110001011010110100100101010111010101010101','01'),'01'))