



"""simple docstring"""




def 						__snake_case						(				SCREAMING_SNAKE_CASE__     :						str						,  SCREAMING_SNAKE_CASE__     :						str    )  ->       bool:





					'''simple docstring'''

					_UpperCAmelCase      :     Tuple        =   len(SCREAMING_SNAKE_CASE__    ) + 1
					_UpperCAmelCase      :     List[str]        =   len(SCREAMING_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      :     int        =   [[0 for i in range(SCREAMING_SNAKE_CASE__    )] for j in range(SCREAMING_SNAKE_CASE__    )]

					# since string of zero length match pattern of zero length
					_UpperCAmelCase      :     List[str]        =   1

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

					# since string of zero length will match with pattern where there
					# is at least one * alternatively
					for j in range(1						,  SCREAMING_SNAKE_CASE__    ):
										_UpperCAmelCase      :     Any        =   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						,  SCREAMING_SNAKE_CASE__    ):
										for j in range(1						,  SCREAMING_SNAKE_CASE__    ):
															if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
																				_UpperCAmelCase      :     str        =   dp[i - 1][j - 1]

															elif pattern[j - 1] == "*":
																				if dp[i][j - 2] == 1:
																									_UpperCAmelCase      :     int        =   1
																				elif pattern[j - 2] in (input_string[i - 1], "."):
																									_UpperCAmelCase      :     Tuple        =   dp[i - 1][j]
																				else:
																									_UpperCAmelCase      :     Any        =   0
															else:
																				_UpperCAmelCase      :     Optional[Any]        =   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 :")

	_lowerCAmelCase    : Optional[Any]							=							"aab"
	_lowerCAmelCase    : Dict							=							"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}")





"""simple docstring"""




from __future__ import annotations

from typing import Any

def 						__snake_case						(				SCREAMING_SNAKE_CASE__     :						list[Any]    )  ->       None:





     '''simple docstring'''

     create_state_space_tree(SCREAMING_SNAKE_CASE__						,  []						,  0    )

def 						__snake_case						(				SCREAMING_SNAKE_CASE__     :						list[Any]						,  SCREAMING_SNAKE_CASE__     :						list[Any]						,  SCREAMING_SNAKE_CASE__     :						int    )  ->       None:





     '''simple docstring'''

     if index == len(SCREAMING_SNAKE_CASE__    ):
          print(SCREAMING_SNAKE_CASE__    )
          return

     create_state_space_tree(SCREAMING_SNAKE_CASE__						,  SCREAMING_SNAKE_CASE__						,  index + 1    )
     current_subsequence.append(sequence[index]    )
     create_state_space_tree(SCREAMING_SNAKE_CASE__						,  SCREAMING_SNAKE_CASE__						,  index + 1    )
     current_subsequence.pop()


if __name__ == "__main__":
 _lowerCAmelCase    : list[Any]							=							[3, 1, 2, 4]
 generate_all_subsequences(seq)

 seq.clear()
 seq.extend(["A", "B", "C"])
 generate_all_subsequences(seq)
