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 :)

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import re\n\ndef encoder(s):\n    d, i, r = {"": 0}, 0, []\n    while i < len(s):\n        x = ""\n        while i < len(s) - 1 and x + s[i] in d:\n            x += s[i]\n            i += 1\n        if x + s[i] not in d:\n            d[x + s[i]] = len(d)\n            r.append((d[x], s[i]))\n        else:\n            r.append((d[x + s[i]], ""))\n        i += 1\n    return "".join(str(x) + y for x, y in r)\n\ndef decoder(s):\n    a, r = [""], []\n    for x, y in re.findall(r"(\\d+)(\\D*)", s):\n        a.append(a[int(x)] + y)\n    return "".join(a)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'encoder'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 7499