



"""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 typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_sentencepiece_available


_lowerCAmelCase    : Union[str, Any]							=							{}

try:
 if not is_sentencepiece_available():
  raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
 pass
else:
 _lowerCAmelCase    : Optional[Any]							=							["GPTSw3Tokenizer"]


if TYPE_CHECKING:
 try:
  if not is_sentencepiece_available():
   raise OptionalDependencyNotAvailable()
 except OptionalDependencyNotAvailable:
  pass
 else:
  from .tokenization_gpt_swa import GPTSwaTokenizer

else:
 import sys

 _lowerCAmelCase    : List[Any]							=							_LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)
