class Compressor(object):
    def __init__(self, window_size, max_code_length):
        self.window_size = window_size
        self.max_code_length = max_code_length

    def find_match(self):
        max_len = 0
        max_offset = 0
        j = 0
        for i in range(self.window_size):
            if self.lookahead[0] == self.window[i]:
                j = 1
                while j < len(self.lookahead) and (i + j) < len(self.window) and self.lookahead[j] == self.window[i + j]:
                    if j > self.max_code_length:
                        break
                    j += 1
                if j > max_len:
                    max_len = j
                    max_offset = i
        return max_offset, max_len

    def compress(self, string):
        self.lookahead = string[:self.max_code_length]
        self.window = ' ' * self.window_size
        output = []
        n = 0
        offset, length = self.find_match()
        while n < len(string):
            if length <= 2:
                output.append(string[n])
                length = 1
            else:
                output.append((offset, length))

            self.window = self.window[length:] + string[n:n + length]
            self.lookahead = self.lookahead[length:] + string[n + self.max_code_length:n + self.max_code_length + length]
            if len(self.lookahead) == 0:
                break

            n += length

            offset, length = self.find_match()

        return output

    def decompress(self, comp):
        result = ' ' * self.window_size
        for c in comp:
            if isinstance(c, str):
                result += c
            else:
                offset, length = c
                base = len(result) - self.window_size + offset
                result += result[base:base + length]
        return result[self.window_size:]