"""simple docstring"""





def 				a_     (      _lowerCAmelCase  : str   , _lowerCAmelCase  : str     ):





       '''simple docstring'''

       lowercase__			:		List[str]       =	len(_lowerCAmelCase     ) + 1
       lowercase__			:		Any       =	len(_lowerCAmelCase     ) + 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.
       lowercase__			:		List[str]       =	[[0 for i in range(_lowerCAmelCase     )] for j in range(_lowerCAmelCase     )]

       # since string of zero length match pattern of zero length
       lowercase__			:		Any       =	1

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

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

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

       _UpperCamelCase   :						Any      =    "aab"
       _UpperCamelCase   :						int      =    "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}''')





def 	lowerCAmelCase       (						lowerCAmelCase_       )->       set:
				lowerCAmelCase_       :					Optional[int]			 = set()
				# edges = list of graph's edges
				lowerCAmelCase_       :					List[str]			 = get_edges(lowerCAmelCase_       )

				# While there are still elements in edges list, take an arbitrary edge
				# (from_node, to_node) and add his extremity to chosen_vertices and then
				# remove all arcs adjacent to the from_node and to_node
				while edges:
								lowerCAmelCase_ ,     lowerCAmelCase_       :					Optional[int]			 = edges.pop()
								chosen_vertices.add(lowerCAmelCase_       )
								chosen_vertices.add(lowerCAmelCase_       )
								for edge in edges.copy():
												if from_node in edge or to_node in edge:
																edges.discard(lowerCAmelCase_       )
				return chosen_vertices



def 	lowerCAmelCase       (						lowerCAmelCase_       )->       set:
				lowerCAmelCase_       :					List[Any]			 = set()
				for from_node, to_nodes in graph.items():
								for to_node in to_nodes:
												edges.add((from_node, to_node)       )
				return edges


if __name__ == "__main__":
						import doctest

						doctest.testmod()

						# graph = {0: [1, 3], 1: [0, 3], 2: [0, 3, 4], 3: [0, 1, 2], 4: [2, 3]}
						# print(f"Matching vertex cover:\n{matching_min_vertex_cover(graph)}")