




'''simple docstring'''







from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_flax_available,
    is_sentencepiece_available,
    is_tf_available,
    is_tokenizers_available,
    is_torch_available,
)


A     ={
    'configuration_albert': ['ALBERT_PRETRAINED_CONFIG_ARCHIVE_MAP', 'AlbertConfig', 'AlbertOnnxConfig'],
}

try:
   if not is_sentencepiece_available():
      raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
   pass
else:
   A     =['AlbertTokenizer']

try:
   if not is_tokenizers_available():
      raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
   pass
else:
   A     =['AlbertTokenizerFast']

try:
   if not is_torch_available():
      raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
   pass
else:
   A     =[
       'ALBERT_PRETRAINED_MODEL_ARCHIVE_LIST',
       'AlbertForMaskedLM',
       'AlbertForMultipleChoice',
       'AlbertForPreTraining',
       'AlbertForQuestionAnswering',
       'AlbertForSequenceClassification',
       'AlbertForTokenClassification',
       'AlbertModel',
       'AlbertPreTrainedModel',
       'load_tf_weights_in_albert',
   ]

try:
   if not is_tf_available():
      raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
   pass
else:
   A     =[
       'TF_ALBERT_PRETRAINED_MODEL_ARCHIVE_LIST',
       'TFAlbertForMaskedLM',
       'TFAlbertForMultipleChoice',
       'TFAlbertForPreTraining',
       'TFAlbertForQuestionAnswering',
       'TFAlbertForSequenceClassification',
       'TFAlbertForTokenClassification',
       'TFAlbertMainLayer',
       'TFAlbertModel',
       'TFAlbertPreTrainedModel',
   ]

try:
   if not is_flax_available():
      raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
   pass
else:
   A     =[
       'FlaxAlbertForMaskedLM',
       'FlaxAlbertForMultipleChoice',
       'FlaxAlbertForPreTraining',
       'FlaxAlbertForQuestionAnswering',
       'FlaxAlbertForSequenceClassification',
       'FlaxAlbertForTokenClassification',
       'FlaxAlbertModel',
       'FlaxAlbertPreTrainedModel',
   ]

if TYPE_CHECKING:
   from .configuration_albert import ALBERT_PRETRAINED_CONFIG_ARCHIVE_MAP, AlbertConfig, AlbertOnnxConfig

   try:
      if not is_sentencepiece_available():
         raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
      pass
   else:
      from .tokenization_albert import AlbertTokenizer

   try:
      if not is_tokenizers_available():
         raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
      pass
   else:
      from .tokenization_albert_fast import AlbertTokenizerFast

   try:
      if not is_torch_available():
         raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
      pass
   else:
      from .modeling_albert import (
          ALBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
          AlbertForMaskedLM,
          AlbertForMultipleChoice,
          AlbertForPreTraining,
          AlbertForQuestionAnswering,
          AlbertForSequenceClassification,
          AlbertForTokenClassification,
          AlbertModel,
          AlbertPreTrainedModel,
          load_tf_weights_in_albert,
      )

   try:
      if not is_tf_available():
         raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
      pass
   else:
      from .modeling_tf_albert import (
          TF_ALBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
          TFAlbertForMaskedLM,
          TFAlbertForMultipleChoice,
          TFAlbertForPreTraining,
          TFAlbertForQuestionAnswering,
          TFAlbertForSequenceClassification,
          TFAlbertForTokenClassification,
          TFAlbertMainLayer,
          TFAlbertModel,
          TFAlbertPreTrainedModel,
      )

   try:
      if not is_flax_available():
         raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
      pass
   else:
      from .modeling_flax_albert import (
          FlaxAlbertForMaskedLM,
          FlaxAlbertForMultipleChoice,
          FlaxAlbertForPreTraining,
          FlaxAlbertForQuestionAnswering,
          FlaxAlbertForSequenceClassification,
          FlaxAlbertForTokenClassification,
          FlaxAlbertModel,
          FlaxAlbertPreTrainedModel,
      )
else:
   import sys

   A     =_LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)










'''simple docstring'''







def 						snake_case_							(_a	:							str    ,   _a	:							str     ):
    UpperCAmelCase			       =		len(_a     ) + 1
    UpperCAmelCase			       =		len(_a     ) + 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(_a     )] for j in range(_a     )]

    # 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    ,   _a     ):
        UpperCAmelCase			       =		0

    # since string of zero length will match with pattern where there
    # is at least one * alternatively
    for j in range(1    ,   _a     ):
        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    ,   _a     ):
        for j in range(1    ,   _a     ):
            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}""")




