def encode(s):
    """Generate LZ77 triples encoding s. The triple (n, k, c) means
    that each of the next n characters is equal to the character k
    places behind it; then the next character after them is c."""
    buffer = ''                 # The input so far
    p = 0                       # Position in buffer of the current chunk
    def triple():
        n = len(buffer) - 1 - p
        k = p - buffer.rindex(buffer[p:-1], 0, -2) if n else 0
        return n, k, buffer[-1]
    for c in s:
        buffer += c
        if buffer[p:] not in buffer[:-1]:
            yield triple()
            p = len(buffer)
    if p < len(buffer):
        yield triple()