


from __future__ import annotations



def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase  )		->				bool:
 UpperCamelCase			:      Optional[int] 			=     get_failure_array(_lowerCAmelCase  )

 # 2) Step through text searching for pattern
 UpperCamelCase			:      Optional[Any] 			=     0, 0  # index into text, pattern
 while i < len(_lowerCAmelCase  ):
  if pattern[j] == text[i]:
   if j == (len(_lowerCAmelCase  ) - 1):
    return True
   j += 1

  # if this is a prefix in our pattern
  # just go back far enough to continue
  elif j > 0:
   UpperCamelCase			:      str 			=     failure[j - 1]
   continue
  i += 1
 return False



def 	A_       (  _lowerCAmelCase  )		->				list[int]:
 UpperCamelCase			:      List[Any] 			=     [0]
 UpperCamelCase			:      List[Any] 			=     0
 UpperCamelCase			:      Union[str, Any] 			=     1
 while j < len(_lowerCAmelCase  ):
  if pattern[i] == pattern[j]:
   i += 1
  elif i > 0:
   UpperCamelCase			:      Optional[int] 			=     failure[i - 1]
   continue
  j += 1
  failure.append(_lowerCAmelCase  )
 return failure


if __name__ == "__main__":
    # Test 1)
    __lowerCamelCase :  Optional[Any]										=  """abc1abc12"""
    __lowerCamelCase :  int										=  """alskfjaldsabc1abc1abc12k23adsfabcabc"""
    __lowerCamelCase :  Tuple										=  """alskfjaldsk23adsfabcabc"""
    assert kmp(pattern, texta) and not kmp(pattern, texta)

    # Test 2)
    __lowerCamelCase :  List[Any]										=  """ABABX"""
    __lowerCamelCase :  Dict										=  """ABABZABABYABABX"""
    assert kmp(pattern, text)

    # Test 3)
    __lowerCamelCase :  Optional[int]										=  """AAAB"""
    __lowerCamelCase :  Any										=  """ABAAAAAB"""
    assert kmp(pattern, text)

    # Test 4)
    __lowerCamelCase :  Optional[Any]										=  """abcdabcy"""
    __lowerCamelCase :  Optional[Any]										=  """abcxabcdabxabcdabcdabcy"""
    assert kmp(pattern, text)

    # Test 5)
    __lowerCamelCase :  str										=  """aabaabaaa"""
    assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]







from typing import TYPE_CHECKING

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


__lowerCamelCase :  int										=  {
    """configuration_convbert""": ["""CONVBERT_PRETRAINED_CONFIG_ARCHIVE_MAP""", """ConvBertConfig""", """ConvBertOnnxConfig"""],
    """tokenization_convbert""": ["""ConvBertTokenizer"""],
}

try:
    if not is_tokenizers_available():
        raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
    pass
else:
    __lowerCamelCase :  Dict										=  ["""ConvBertTokenizerFast"""]

try:
    if not is_torch_available():
        raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
    pass
else:
    __lowerCamelCase :  int										=  [
        """CONVBERT_PRETRAINED_MODEL_ARCHIVE_LIST""",
        """ConvBertForMaskedLM""",
        """ConvBertForMultipleChoice""",
        """ConvBertForQuestionAnswering""",
        """ConvBertForSequenceClassification""",
        """ConvBertForTokenClassification""",
        """ConvBertLayer""",
        """ConvBertModel""",
        """ConvBertPreTrainedModel""",
        """load_tf_weights_in_convbert""",
    ]


try:
    if not is_tf_available():
        raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
    pass
else:
    __lowerCamelCase :  str										=  [
        """TF_CONVBERT_PRETRAINED_MODEL_ARCHIVE_LIST""",
        """TFConvBertForMaskedLM""",
        """TFConvBertForMultipleChoice""",
        """TFConvBertForQuestionAnswering""",
        """TFConvBertForSequenceClassification""",
        """TFConvBertForTokenClassification""",
        """TFConvBertLayer""",
        """TFConvBertModel""",
        """TFConvBertPreTrainedModel""",
    ]


if TYPE_CHECKING:
    from .configuration_convbert import CONVBERT_PRETRAINED_CONFIG_ARCHIVE_MAP, ConvBertConfig, ConvBertOnnxConfig
    from .tokenization_convbert import ConvBertTokenizer

    try:
        if not is_tokenizers_available():
            raise OptionalDependencyNotAvailable()
    except OptionalDependencyNotAvailable:
        pass
    else:
        from .tokenization_convbert_fast import ConvBertTokenizerFast

    try:
        if not is_torch_available():
            raise OptionalDependencyNotAvailable()
    except OptionalDependencyNotAvailable:
        pass
    else:
        from .modeling_convbert import (
            CONVBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
            ConvBertForMaskedLM,
            ConvBertForMultipleChoice,
            ConvBertForQuestionAnswering,
            ConvBertForSequenceClassification,
            ConvBertForTokenClassification,
            ConvBertLayer,
            ConvBertModel,
            ConvBertPreTrainedModel,
            load_tf_weights_in_convbert,
        )

    try:
        if not is_tf_available():
            raise OptionalDependencyNotAvailable()
    except OptionalDependencyNotAvailable:
        pass
    else:
        from .modeling_tf_convbert import (
            TF_CONVBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
            TFConvBertForMaskedLM,
            TFConvBertForMultipleChoice,
            TFConvBertForQuestionAnswering,
            TFConvBertForSequenceClassification,
            TFConvBertForTokenClassification,
            TFConvBertLayer,
            TFConvBertModel,
            TFConvBertPreTrainedModel,
        )


else:
    import sys

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