def build_prefix_table(pattern):
	"""
	Helper function to build a prefix table - stores length of longest prefix suffix ending at each index in pattern

	Time complexity: O(n), n = Length of pattern

	Space complexity: O(n), n = Length of pattern
	"""

	prefix_table = []
	if len(pattern) > 0:
		prefix_table.append(0)
		previous_length = 0
		i = 1
		while i < len(pattern):
			if pattern[i] == pattern[previous_length]:
				prefix_table.append(previous_length + 1)
				previous_length += 1
				i += 1
			else:
				if previous_length != 0:
					previous_length = prefix_table[previous_length - 1]
				else:
					prefix_table.append(0)
					i += 1
	return prefix_table