def encodeNumber(n, maxLookback)
	if maxLookback > 95 * 95
		a0 = (n / 95 / 95).floor
		a1 = ((n - (a0 * 95 * 95)) / 95).floor
		a2 = n - (a0 * 95 * 95) - (a1 * 95)
		return (a0 + 33).chr + (a1 + 32).chr + (a2 + 32).chr
	else
		a0 = (n / 95).floor
		a1 = n - (a0 * 95)
		return (a0 + 33).chr + (a1 + 32).chr
	end
end

def lzip(data, maxLookback = 950)
	# How many bytes do we reserve for references?
	if maxLookback > 95 * 95
		referenceBytes = 6
	else
		referenceBytes = 4
	end
	
	# Store it in the output so that it can be decompressed correctly
	output = referenceBytes.to_s
	
	# We need the first few bytes regardless, so start after the first 4 or so
	output += data[0..3]
	i = 4
	# Now loop through the data...
	while i < data.length
		# $best contains an array, keeping the position and how much identical data was found
		best = [-1, -1]
		
		# Find some identical characters as we're currently at
		j = data.index(data[i..i + referenceBytes])
		#~ j = [0, i - maxLookback].max
		if j != nil # The data occurred before!
			while j < i - referenceBytes # loop through the data from where the data was found till where we are
				beginpos = j
				len = 0
				# Find how many bytes repeat (if any)
				while beginpos + len < i && data[beginpos + len..beginpos + len] == data[i + len..i + len]
					len += 2
				end
				if data[beginpos + len - 1..beginpos + len - 1] != data[i + len - 1..i + len - 1]
					len -= 1
				end
				if (len > referenceBytes && len > best[1])
					best = [beginpos, len]
				end
				#~ j = data[j + 1..i].index(data[i..i + referenceBytes])
				j += 1
			end
		end
		# we found a place where the data occurred before, and it's actually long enough that it's worth to reference it
		if best[1] > referenceBytes
			output += " "
			output += encodeNumber(best[0], maxLookback)
			output += encodeNumber(best[1], maxLookback)
			i += best[1] - 1
		else
			if data[i..i] == " "
				output += "  "
			else
				output += data[i..i]
			end
		end
		i += 1
		#print data[i..i]
	end
	return output
end


def lzipv2(data, maxLookback = 950)
	# How many bytes do we reserve for references?
	if maxLookback > 95 * 95
		referenceBytes = 6
	else
		referenceBytes = 4
	end
	
	# Store it in the output so that it can be decompressed correctly
	output = referenceBytes.to_s
	
	# We need the first few bytes regardless, so start after the first 4 or so
	output += data[0..3]
	i = 4
	# Now loop through the data...
	while i < data.length
		# $best contains an array, keeping the position and how much identical data was found
		best = [-1, -1]
		
		# Find some identical characters as we're currently at
		#~ j = data.index(data[i..i + referenceBytes])
		if data.index(data[i..i + referenceBytes]) != nil
			j = [0, i - maxLookback].max
			while j < i - referenceBytes # loop through the data from where the data was found till where we are
				beginpos = j
				len = 0
				# Find how many bytes repeat (if any)
				while beginpos + len < i && data[beginpos + len..beginpos + len] == data[i + len..i + len]
					len += 1
				end
				#~ if data[beginpos + len - 1..beginpos + len - 1] != data[i + len - 1..i + len - 1]
					#~ len -= 1
				#~ end
				if (len > referenceBytes && len > best[1])
					best = [beginpos, len]
				end
				#~ j = data[j + 1..i].index(data[i..i + referenceBytes])
				j += 1
			end
		end
		# we found a place where the data occurred before, and it's actually long enough that it's worth to reference it
		if best[1] > referenceBytes
			output += " "
			output += encodeNumber(best[0], maxLookback)
			output += encodeNumber(best[1], maxLookback)
			i += best[1] - 1
		else
			if data[i..i] == " "
				output += "  "
			else
				output += data[i..i]
			end
		end
		i += 1
		#print data[i..i]
	end
	return output
end

if ARGV[0] == "run"
	data = open(ARGV[1], "rb") {|io| io.read }
	print lzipv2(data, 9090909090)
else
	testcase1 = open("../_private/testcase1", "rb") {|io| io.read }
	solution1 = open("../_private/solution1", "rb") {|io| io.read }
	testcase2 = open("../_private/testcase2", "rb") {|io| io.read }
	solution2 = open("../_private/solution2", "rb") {|io| io.read }
	time = Time.now
	print lzip(testcase1) == solution1
	print " " + (Time.now - time).to_f.to_s
	print "\n"
	time = Time.now
	print lzip(testcase2) == solution2
	print " " + (Time.now - time).to_f.to_s
	print "\n"
end




#~ class Compressor
  #~ 
  #~ def self.encodeNumber(n)
    #~ a0 = (n / 95 / 95).floor
    #~ a1 = ((n - (a0 * 95 * 95)) / 95).floor
    #~ a2 = n - (a0 * 95 * 95) - (a1 * 95)
    #~ return (a0 + 33).chr + (a1 + 32).chr + (a2 + 32).chr
  #~ end
#~ 
  #~ def self.lzip(data)
    #~ output = data.split('')[0]
    #~ i = 1
    #~ while i < data.length
      #~ best = [-1, -1]
      #~ j = 0
      #~ while j < i - 5
        #~ beginpos = j
        #~ pos = j
        #~ while pos < i && data.split('')[pos] == data.split('')[i + (pos - beginpos)]
          #~ pos+=1
        #~ end
        #~ len = pos - beginpos
        #~ if (len > 6 && len > best[1])
          #~ best = [beginpos, len]
        #~ end
        #~ j = j + 1
      #~ end
      #~ 
      #~ if best[1] > 6
        #~ output += " "
        #~ output += encodeNumber(best[0])
        #~ output += encodeNumber(best[1])
        #~ i += best[1] - 1
      #~ else
        #~ if data[i] == " "
          #~ output += "  "
        #~ else
          #~ output += data.split('')[i]
        #~ end
      #~ end
      #~ i = i + 1
    #~ end
    #~ return output
  #~ end
#~ end