import collections
import math


def examineSubstrings(data, length, z=3.0, dividerMultiple=20.0):
	"""
	Examines substrings of the data of a given length, looking for patterns.

	:param data: bytes
	:param length: int Substring length to examine
	:param z: float
	:param dividerMultiple: float
	:return: collections.Counter
	"""
	#Count values in a sliding window over the data
	total = len(data) - length
	window = (data[k:k+length] for k in range(total))
	counts = collections.Counter(window)
	print((' %s Byte Substrings ' % length).center(100, '*'))
	print()
	print('%10s %s' % (total, 'Total'))
	for values, count in counts.most_common(20):
		if count <= 1:
			break
		print('%10s %30s %s' % (count, values, tuple(value for value in values)))
	print()

	#If a value is more common than expected, it may be a divider that separates tokens
	for common, commonCount in counts.most_common(5):
		#Statistically, this means we are looking for values where the lower end of the
		#proportion confidence interval is still sufficiently high.
		#
		#To compute that, remember the formula for the confidence interval:
		#	p_hat +/- z * sqrt(p_hat * (1 - p_hat) / n)
		fraction = float(commonCount) / total
		conservativeFraction = fraction - z * math.sqrt(fraction * (1.0 - fraction) / total)
		expectedFraction = 1.0 / (256 ** length)

		#Skip anything that doesn't happen at least the token multiple more often than expected
		if conservativeFraction < dividerMultiple * expectedFraction:
			break

		#Look for common tokens, skipping if there are none
		tokens = data.split(common)
		tokenCounts = collections.Counter(tokens)
		if tokenCounts.most_common(1)[0][1] == 1:
			continue

		print(' Common Tokens '.center(60, '*'))
		print('Common divider found: %s %s (%d times)' % (common, tuple(common), commonCount))
		print()
		for token, count in tokenCounts.most_common(20):
			if count <= 1:
				break
			print('%10s   %30s %s' % (count, token, tuple(token)))
		print()

	return counts