




from __future__ import annotations

from scipy.special import comb  # type: ignore




class       _A				:






		def __init__(    self						,		_SCREAMING_SNAKE_CASE			):
								_UpperCAmelCase      =			list_of_points
								# Degree determines the flexibility of the curve.
								# Degree = 1 will produce a straight line.
								_UpperCAmelCase      =			len(_SCREAMING_SNAKE_CASE			) - 1






		def 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE			):
								assert 0 <= t <= 1, "Time t must be between 0 and 1."
								_UpperCAmelCase      =			[]
								for i in range(len(self.list_of_points			)			):
														# basis function for each i
														output_values.append(
														    comb(self.degree						,		_SCREAMING_SNAKE_CASE			) * ((1 - t) ** (self.degree - i)) * (t**i)			)
								# the basis must sum up to 1 for it to produce a valid Bezier curve.
								assert round(sum(_SCREAMING_SNAKE_CASE			)						,		5			) == 1
								return output_values






		def 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE			):
								assert 0 <= t <= 1, "Time t must be between 0 and 1."

								_UpperCAmelCase      =			self.basis_function(_SCREAMING_SNAKE_CASE			)
								_UpperCAmelCase      =			0.0
								_UpperCAmelCase      =			0.0
								for i in range(len(self.list_of_points			)			):
														# For all points, sum up the product of i-th basis function and i-th point.
														x += basis_function[i] * self.list_of_points[i][0]
														y += basis_function[i] * self.list_of_points[i][1]
								return (x, y)






		def 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE = 0.01			):
								from matplotlib import pyplot as plt  # type: ignore

								_UpperCAmelCase      =			[]  # x coordinates of points to plot
								_UpperCAmelCase      =			[]  # y coordinates of points to plot

								_UpperCAmelCase      =			0.0
								while t <= 1:
														_UpperCAmelCase      =			self.bezier_curve_function(_SCREAMING_SNAKE_CASE			)
														to_plot_x.append(value[0]			)
														to_plot_y.append(value[1]			)
														t += step_size

								_UpperCAmelCase      =			[i[0] for i in self.list_of_points]
								_UpperCAmelCase      =			[i[1] for i in self.list_of_points]

								plt.plot(
								    _SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE						,		color="""blue"""						,		label="""Curve of Degree """ + str(self.degree			)						,		)
								plt.scatter(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE						,		color="""red"""						,		label="""Control Points"""			)
								plt.legend()
								plt.show()


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				BezierCurve([(1, 2), (3, 5)]).plot_curve()  # degree 1
				BezierCurve([(0, 0), (5, 5), (5, 0)]).plot_curve()  # degree 2
				BezierCurve([(0, 0), (5, 5), (5, 0), (2.5, -2.5)]).plot_curve()  # degree 3





def        _SCREAMING_SNAKE_CASE      (		snake_case			,     snake_case       )						->				bool:
						_UpperCAmelCase      =			len(snake_case       ) + 1
						_UpperCAmelCase      =			len(snake_case       ) + 1

						# dp is a 2d matrix where dp[i][j] denotes whether prefix string of
						# length i of input_string matches with prefix string of length j of
						# given pattern.
						# "dp" stands for dynamic programming.
						_UpperCAmelCase      =			[[0 for i in range(snake_case       )] for j in range(snake_case       )]

						# since string of zero length match pattern of zero length
						_UpperCAmelCase      =			1

						# since pattern of zero length will never match with string of non-zero length
						for i in range(1			,     snake_case       ):
												_UpperCAmelCase      =			0

						# since string of zero length will match with pattern where there
						# is at least one * alternatively
						for j in range(1			,     snake_case       ):
												_UpperCAmelCase      =			dp[0][j - 2] if pattern[j - 1] == """*""" else 0

						# now using bottom-up approach to find for all remaining lengths
						for i in range(1			,     snake_case       ):
												for j in range(1			,     snake_case       ):
																		if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
																								_UpperCAmelCase      =			dp[i - 1][j - 1]

																		elif pattern[j - 1] == "*":
																								if dp[i][j - 2] == 1:
																														_UpperCAmelCase      =			1
																								elif pattern[j - 2] in (input_string[i - 1], "."):
																														_UpperCAmelCase      =			dp[i - 1][j]
																								else:
																														_UpperCAmelCase      =			0
																		else:
																								_UpperCAmelCase      =			0

						return bool(dp[-1][-1]       )


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				# inputing the strings
				# input_string = input("input a string :")
				# pattern = input("input a pattern :")

				a													=			"aab"
				a													=			"c*a*b"

				# using function to check whether given string matches the given pattern
				if match_pattern(input_string, pattern):
								print(F'{input_string} matches the given pattern {pattern}')
				else:
								print(F'{input_string} does not match with the given pattern {pattern}')