






'''simple docstring'''







from __future__ import annotations

import matplotlib.pyplot as plt  # type: ignore
import numpy

# initial triangle of Koch snowflake
__lowerCAmelCase									=   numpy.array([0, 0])
__lowerCAmelCase									=   numpy.array([0.5, 0.8660254])
__lowerCAmelCase									=   numpy.array([1, 0])
__lowerCAmelCase									=   [VECTOR_1, VECTOR_2, VECTOR_3, VECTOR_1]





def 		_UpperCAmelCase (				__A				: list[numpy.ndarray]    ,		__A				: int   ):
				a_		:	List[Any]									=   initial_vectors
				for _ in range(__A   ):
								a_		:	Optional[Any]									=   iteration_step(__A   )
				return vectors





def 		_UpperCAmelCase (				__A				: list[numpy.ndarray]   ):
				a_		:	str									=   []
				for i, start_vector in enumerate(vectors[:-1]   ):
								a_		:	List[str]									=   vectors[i + 1]
								new_vectors.append(__A   )
								a_		:	Optional[Any]									=   end_vector - start_vector
								new_vectors.append(start_vector + difference_vector / 3   )
								new_vectors.append(
								    start_vector + difference_vector / 3 + rotate(difference_vector / 3    ,		60   )   )
								new_vectors.append(start_vector + difference_vector * 2 / 3   )
				new_vectors.append(vectors[-1]   )
				return new_vectors





def 		_UpperCAmelCase (				__A				: numpy.ndarray    ,		__A				: float   ):
				a_		:	List[str]									=   numpy.radians(__A   )
				a_					,      a_		:	str									=   numpy.cos(__A   ), numpy.sin(__A   )
				a_		:	List[Any]									=   numpy.array(((c, -s), (s, c))   )
				return numpy.dot(__A    ,		__A   )





def 		_UpperCAmelCase (				__A				: list[numpy.ndarray]   ):
				a_		:	str									=   plt.gca()
				axes.set_aspect('''equal'''   )

				# matplotlib.pyplot.plot takes a list of all x-coordinates and a list of all
				# y-coordinates as inputs, which are constructed from the vector-list using
				# zip()
				a_					,      a_		:	Any									=   zip(*__A   )
				plt.plot(__A    ,		__A   )
				plt.show()


if __name__ == "__main__":
		import doctest

		doctest.testmod()

		__lowerCAmelCase									=   iterate(INITIAL_VECTORS, 5)
		plot(processed_vectors)












'''simple docstring'''







from __future__ import annotations





def 		_UpperCAmelCase (				__A				: str    ,		__A				: str   ):
				a_		:	int									=   get_failure_array(__A   )

				# 2) Step through text searching for pattern
				a_					,      a_		:	Any									=   0, 0  # index into text, pattern
				while i < len(__A   ):
								if pattern[j] == text[i]:
												if j == (len(__A   ) - 1):
																return True
												j += 1

								# if this is a prefix in our pattern
								# just go back far enough to continue
								elif j > 0:
												a_		:	Any									=   failure[j - 1]
												continue
								i += 1
				return False





def 		_UpperCAmelCase (				__A				: str   ):
				a_		:	Optional[Any]									=   [0]
				a_		:	Any									=   0
				a_		:	int									=   1
				while j < len(__A   ):
								if pattern[i] == pattern[j]:
												i += 1
								elif i > 0:
												a_		:	List[Any]									=   failure[i - 1]
												continue
								j += 1
								failure.append(__A   )
				return failure


if __name__ == "__main__":
		# Test 1)
		__lowerCAmelCase									=   'abc1abc12'
		__lowerCAmelCase									=   'alskfjaldsabc1abc1abc12k23adsfabcabc'
		__lowerCAmelCase									=   'alskfjaldsk23adsfabcabc'
		assert kmp(pattern, texta) and not kmp(pattern, texta)

		# Test 2)
		__lowerCAmelCase									=   'ABABX'
		__lowerCAmelCase									=   'ABABZABABYABABX'
		assert kmp(pattern, text)

		# Test 3)
		__lowerCAmelCase									=   'AAAB'
		__lowerCAmelCase									=   'ABAAAAAB'
		assert kmp(pattern, text)

		# Test 4)
		__lowerCAmelCase									=   'abcdabcy'
		__lowerCAmelCase									=   'abcxabcdabxabcdabcdabcy'
		assert kmp(pattern, text)

		# Test 5)
		__lowerCAmelCase									=   'aabaabaaa'
		assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]




