

"""simple docstring"""


class      __a							:






     '''simple docstring'''

     def __init__(						self	,    _a	,    _a	,    _a  )  ->      str:


           """simple docstring"""


           SCREAMING_SNAKE_CASE__   :      Any      		=	name
           SCREAMING_SNAKE_CASE__   :      Optional[Any]      		=	value
           SCREAMING_SNAKE_CASE__   :      List[Any]      		=	weight

     def __repr__(						self  )  ->      List[Any]:


           """simple docstring"""


           return f'''{self.__class__.__name__}({self.name}, {self.value}, {self.weight})'''

     def 					_a			(						self  )  ->      Dict:


           """simple docstring"""


           return self.value

     def 					_a			(						self  )  ->      int:


           """simple docstring"""


           return self.name

     def 					_a			(						self  )  ->      Optional[Any]:


           """simple docstring"""


           return self.weight





     def 					_a			(						self  )  ->      Dict:


           """simple docstring"""


           return self.value / self.weight





def  _lowercase					(    __lowerCAmelCase  ,					__lowerCAmelCase  ,					__lowerCAmelCase							)       ->				Dict:
      SCREAMING_SNAKE_CASE__   :      Any      		=	[]
      for i in range(len(__lowerCAmelCase							)							):
            menu.append(Things(name[i]  ,					value[i]  ,					weight[i]							)							)
      return menu




def  _lowercase					(    __lowerCAmelCase  ,					__lowerCAmelCase  ,					__lowerCAmelCase							)       ->				Union[str, Any]:
      SCREAMING_SNAKE_CASE__   :      Optional[Any]      		=	sorted(__lowerCAmelCase  ,					key=__lowerCAmelCase  ,					reverse=__lowerCAmelCase							)
      SCREAMING_SNAKE_CASE__   :      str      		=	[]
      SCREAMING_SNAKE_CASE__		,		SCREAMING_SNAKE_CASE__   :      Optional[int]      		=	0.0, 0.0
      for i in range(len(__lowerCAmelCase							)							):
            if (total_cost + items_copy[i].get_weight()) <= max_cost:
                  result.append(items_copy[i]							)
                  total_cost += items_copy[i].get_weight()
                  total_value += items_copy[i].get_value()
      return (result, total_value)




def  _lowercase					(    )       ->				List[str]:
      pass


if __name__ == "__main__":
  import doctest

  doctest.testmod()







"""simple docstring"""


def  _lowercase					(    __lowerCAmelCase  ,					__lowerCAmelCase							)       ->				bool:
      SCREAMING_SNAKE_CASE__   :      Optional[Any]      		=	len(__lowerCAmelCase							) + 1
      SCREAMING_SNAKE_CASE__   :      int      		=	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.
      SCREAMING_SNAKE_CASE__   :      Dict      		=	[[0 for i in range(__lowerCAmelCase							)] for j in range(__lowerCAmelCase							)]

      # since string of zero length match pattern of zero length
      SCREAMING_SNAKE_CASE__   :      Dict      		=	1

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

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

                  elif pattern[j - 1] == "*":
                        if dp[i][j - 2] == 1:
                              SCREAMING_SNAKE_CASE__   :      List[str]      		=	1
                        elif pattern[j - 2] in (input_string[i - 1], "."):
                              SCREAMING_SNAKE_CASE__   :      List[Any]      		=	dp[i - 1][j]
                        else:
                              SCREAMING_SNAKE_CASE__   :      Optional[int]      		=	0
                  else:
                        SCREAMING_SNAKE_CASE__   :      Dict      		=	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					:Any    = "aab"
  a					:Optional[Any]    = "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}')




