In this kata, you need to make a (simplified) LZ78 encoder and decoder.
[LZ78](https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ78) is a dictionary-based compression method created in 1978. You will find a  detailed explanation about how it works below.

The input parameter will always be a non-empty string of upper case alphabetical characters. The maximum decoded string length is 1000 characters.


# Instructions

*If anyone has any ideas on how to make the instructions shorter / clearer, that would be greatly appreciated.*

If the below explanation is too confusing, just leave a comment and I'll be happy to help.

---

The input is looked at letter by letter.
Each letter wants to be matched with the longest dictionary substring at that current time.

The output is made up of tokens.
Each token is in the format ``
where `index` is the index of the longest dictionary value that matches the current substring
and `letter` is the current letter being looked at.


Here is how the string `'ABAABABAABAB'` is encoded:


* First, a dictionary is initialised with the 0th item pointing to an empty string:

```md
Dictionary      Input             Output
0  |  ''        ABAABABAABAB
```

* The first letter is `A`. As it doesn't appear in the dictionary, we add `A` to the next avaliable index.
The token `<0, A>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A>
1  |  A         ^
```

* The second letter is `B`. It doesn't appear in the dictionary, so we add `B` to the next avaliable index.
The token `<0, B>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B>
1  |  A          ^
2  |  B
```

* The third letter is `A` again: it already appears in the dictionary at position `1`. We add the next letter which is also `A`. `AA` doesn't appear in the dictionary, so we add it to the next avaliable index.
The token `<1, A>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B> <1, A>
1  |  A           ^^
2  |  B
3  |  AA
```

* The next letter is `B` again: it already appears in the dictionary at position `2`. We add the next letter which is `A`. `BA` doesn't appear in the dictionary, so we add it to the next avaliable index.
The token `<2, A>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B> <1, A> <2, A>
1  |  A             ^^
2  |  B
3  |  AA
4  |  BA
```

* The next letter is `B`: it already appears in the dictionary and at position `2`. We add the next letter which is `A`. `BA` already appears in the dictionary at position `4`. We add the next letter which is `A`. `BAA` doesn't appear in the dictionary, so we add it to the next avaliable index.
The token `<4, A>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B> <1, A> <2, A> <4, A>
1  |  A               ^^^
2  |  B
3  |  AA
4  |  BA
5  |  BAA
```

* The next letter is `B`. It already appears in the dictionary at position `2`. We add the next letter which is `A`. `BA` already appears in the dictionary at position `4`. We add the next letter which is `B`. `BAB` doesn't appear in the dictionary, so we add it to the next avaliable index.
The token `<4, B>` is added to the output:

```md
Dictionary      Input             Output

0  |  ''        ABAABABAABAB      <0, A> <0, B> <1, A> <2, A> <4, A> <4, B>
1  |  A                  ^^^
2  |  B
3  |  AA
4  |  BA
5  |  BAA
6  |  BAB
```

* We have now reached the end of the string. We have the output tokens: `<0, A> <0, B> <1, A> <2, A> <4, A> <4, B>`.
Now we just return the tokens without the formatting: `'0A0B1A2A4A4B'`

**Note:**

If the string ends with a match in the dictionary, the last token should only contain the index of the dictionary. For example, `'ABAABABAABABAA'` (same as the example but with `'AA'` at the end) should return `'0A0B1A2A4A4B3'` (note the final `3`).

To decode, it just works the other way around.


# Examples

Some more examples:
```
Decoded                               Encoded

ABBCBCABABCAABCAABBCAA                0A0B2C3A2A4A6B6
AAAAAAAAAAAAAAA                       0A1A2A3A4A
ABCABCABCABCABCABC                    0A0B0C1B3A2C4C7A6
ABCDDEFGABCDEDBBDEAAEDAEDCDABC        0A0B0C0D4E0F0G1B3D0E4B2D10A1E4A10D9A2C
```


Good luck :)

Difficulty: introductory

Starter code:

def encoder(data):
	

Solutions:
import re

def encoder(s):
    d, out, it = {},[], iter(s)
    for c in it:
        i,k = 0,c
        while k in d: 
            i,c = d[k], next(it,'')
            if not c: break
            k += c
        d[k] = len(d)+1
        out.append(f'{i}{c}')
    return ''.join(out)


def decoder(s):
    d = ['']
    for m in re.finditer(r'(\d+)(\D?)',s):
        d.append( d[int(m[1])] + m[2] )
    return ''.join(d)

def encoder(data):

    def get_key_by_value(value):
        for key in dictionary:
            if dictionary[key] == value:
                return key

    dictionary = {0: ''}
    dict_index = 1
    substring = ''
    encoded = []

    for char in data:
        substring += char
        if substring not in list(dictionary.values()):
            dictionary[dict_index] = substring
            encoded.append(str(get_key_by_value(substring[:-1])))
            encoded.append(substring[-1])
            dict_index += 1
            substring = ''
    if substring != '':
        encoded.append(str(get_key_by_value(substring)))
    return ''.join(encoded)


def decoder(data):
    dictionary = {0: ''}
    dict_index = 1
    decoded = []
    key = ''
    for char in data:
        if char.isdigit():
            key += char
        else:
            substring = dictionary[int(key)] + char
            dictionary[dict_index] = substring
            dict_index += 1
            decoded.append(substring)
            key = ''
    if key != '':
        decoded.append(dictionary[int(key)])
    return ''.join(decoded)


from re import findall

def encoder(data):
    base = ""
    dictionary = {base: 0}
    output = []
    
    for char in data:
        curr = base + char
        if curr in dictionary:
            base = curr
        else:
            output.append(f"{dictionary[base]}{char}")
            dictionary[curr] = len(dictionary)
            base = ""
    
    if base:
        output.append(f"{dictionary[base]}")
    
    return "".join(output)


def decoder(data):
    dictionary = [""]
    
    for idx, char in findall("(\d+)([A-Z]?)", data):
        dictionary.append(dictionary[int(idx)] + char)
    
    return "".join(dictionary)

def encoder(data):
    d, d_reverse = {0: ''}, {'': 0}
    d_idx, data_idx = 1, 0
    while data_idx < len(data):
        if data[data_idx] not in d_reverse:
            d[d_idx] = '0' + data[data_idx]
            d_reverse[data[data_idx]] = d_idx
        else:
            start_idx = data_idx
            while data_idx + 1 < len(data) and data[start_idx: data_idx + 1] in d_reverse:
                data_idx += 1
            if data_idx == len(data) - 1:
                if data[start_idx: data_idx + 1] in d_reverse:
                    d[d_idx] = str(d_reverse[data[start_idx:data_idx+1]])
                else:
                    d[d_idx] = str(d_reverse[data[start_idx:data_idx]]) + data[data_idx]
                break
            else:
                d[d_idx] = str(d_reverse[data[start_idx:data_idx]]) + data[data_idx]
                d_reverse[data[start_idx:data_idx+1]] = d_idx
        data_idx += 1
        d_idx += 1
    return ''.join([v for k, v in list(d.items()) if k != 0])


def decoder(data):
    d, s = [], []
    for i in range(len(data)):
        if i == len(data)-1 and data[i].isdigit():
            s.append(data[-1])
            d.append([int(''.join(s)), ''])
        if data[i].isalpha():
            d.append([int(''.join(s)), data[i]])
            s = []
        else:
            s.append(data[i])
    d_list = []
    for i in range(len(d)):
        if i == len(d) - 1 and not d[i][1]:
            d_list.append(d_list[d[i][0]-1])
            break
        if d[i][0] == 0:
            d_list.append(d[i][1])
        else:
            d_list.append(d_list[d[i][0]-1] + d[i][1])
    return ''.join(d_list)


import re
def encoder(s):
    d, numbers, i, li = {}, iter(range(1, 1000)), 0, []
    while i < len(s):
        symbol = s[i]
        prev = 0
        while symbol in d:
            i += 1 ; prev = d[symbol]
            if i == len(s) : return "".join(li)+str(d[symbol])
            symbol += s[i]
        d[symbol] = next(numbers)
        li.append(str(prev) + s[i])
        i += 1
    return "".join(li)
    
def decoder(s):
    parts, numbers, d, li = re.findall(r'\d+[A-Z]', s), iter(range(1, 1000)), {}, []
    for i in parts:
        if re.fullmatch(r'\d+\w', i):
            t = re.findall(r'(\d+)(\w)',i)
            k, l = int(t[0][0]), t[0][1]
            if not k : d[next(numbers)] = l ; li.append(l)
            else : d[next(numbers)] = d[k] + l ; li.append(d[k] + l)
        else : li.append(d[int(i)])
    p = len(s)-len(''.join(parts))
    return ''.join(li) + (d[int(s[-p:])] if s[-p:].isdigit() else '')

def encoder(data):
    d,c,o=[''],'',''
    for i in data: d,c,o=(d,c+i,o)if c+i in d else(d+[c+i],'',o+str(d.index(c))+i)
    return o+(str(d.index(c)) if c else '')

def decoder(data):
    d,c,o=[''],'',''
    for i in data: d,c,o=(d,c+i,o)if i in '0123456789' else(d+[d[int(c)]+i],'',o+d[int(c)]+i)
    return o+(d[int(c)] if c else '')


import re
def encoder(data):
    dct = {'':0}
    search = ''
    output = '' 
    for i in range(len(data)):
        search += data[i]
        if search not in dct:
            dct[search] = len(dct)
            output += f'{dct[search[:-1]]}{search[-1]}'
            search = ''
        try:
            search + data[i+1]
        except IndexError:
            if search == data[-(len(search)):]:
                output += f'{dct[search]}'           
    return output

def decoder(data):
    dct = {0:''}
    output = ''
    lsnb = re.findall(r'\d+', data)
    lsch = re.findall(r'[A-Z]', data)
    for i in range(len(lsnb)):
        try:
            lsch[i]
            dct[len(dct)] = dct[int(lsnb[i])] + lsch[i]
            output += dct[len(dct)-1]        
        except IndexError:
            output += dct[int(lsnb[i])]
    return output  

import re

def encoder(s):
    d, i, r = {"": 0}, 0, []
    while i < len(s):
        x = ""
        while i < len(s) - 1 and x + s[i] in d:
            x += s[i]
            i += 1
        if x + s[i] not in d:
            d[x + s[i]] = len(d)
            r.append((d[x], s[i]))
        else:
            r.append((d[x + s[i]], ""))
        i += 1
    return "".join(str(x) + y for x, y in r)

def decoder(s):
    a, r = [""], []
    for x, y in re.findall(r"(\d+)(\D*)", s):
        a.append(a[int(x)] + y)
    return "".join(a)

import re
def encoder(data):
    dictionary = { '': 0 }
    output = []
    index = 1
    longest_match = ""
    substring = ""    
    for character in data:
        substring += character
        if substring not in dictionary:
            dictionary[substring] = index
            output.append((dictionary[longest_match], character))
            longest_match = ""
            substring = ""
            index += 1
        else:
            longest_match += character
    if substring in dictionary and substring != "":
        output.append((dictionary[substring], ''))

    return ''.join(str(i)+j for i,j in output)



def decoder(data):
    dictionary = { 0: '' }
    last = re.search(r'(\d*)$', data).group()    
    data = re.findall(r'(\d+)([A-Z])', data)
    if last != "":
        data.append((last, ""))
    index = 1
    for pair in data:
        dictionary[index] = dictionary[int(pair[0])] + pair[1]
        index += 1    
    return ''.join(dictionary.values())

def encoder(data):
    dicto, store, i, f = {0: ""}, "", 0, ""
    save = 0
    while i <= len(data):
        if i == len(data) and store in list(dicto.values()):
            for k in dicto:
                if dicto[k] == store and store != "":
                    f += f"{k}"
            return f
        if store not in list(dicto.values()) and store != "":
            dicto[max(dicto.keys())+1] = store
            f += f"{save}{data[i-1]}"
            store = ""
            if i == len(data):
                return f
            continue
        if data[i] not in list(dicto.values()) and store == "":
            save = 0
            for m in dicto:
                if dicto[m] == store:
                    save = m
            dicto[max(dicto.keys())+1] = data[i]
            f += f"{save}{data[i]}"
            i += 1
        else:
            for m in dicto:
                if dicto[m] == store:
                    save = m
                elif dicto[m] == data[i] and store == "":
                    save = m
            store += data[i]
            i += 1
    return f


def decoder(data):
    dc, dic = "", {0: ""}
    i = 0
    while i <= len(data)-1:

        if data[i].isdigit() and i == len(data)-1:
            dc += dic[int(data[i])]
            return dc
        if data[i] == "0":
            dc += data[i+1]
            dic[max(dic.keys())+1] = data[i+1]
            i += 1
        elif data[i] != "0" and data[i].isdigit() and not data[i+1].isdigit():
            c = dic[int(data[i])]+data[i+1]
            dc += c
            dic[max(dic.keys())+1] = c
            i += 1
        elif data[i].isdigit() and data[i+1].isdigit():
            acc = data[i]
            while data[i+1].isdigit():
                i += 1
                acc += data[i]
                if i+1 == len(data):
                    dc += dic[int(acc)]
                    return dc
            dc += dic[int(acc)]+data[i+1]
            dic[max(dic.keys())+1] = dic[int(acc)]+data[i+1]
            i += 1
        else:
            i += 1

    return dc