






lowerCamelCase      :       Tuple    =						256
# Modulus to hash a string
lowerCamelCase      :       Optional[int]    =						1000003





def    __lowerCAmelCase   (    __snake_case       ,			__snake_case							):
     __lowerCAmelCase             =       len(__snake_case							)
     __lowerCAmelCase             =       len(__snake_case							)
     if p_len > t_len:
          return False

     __lowerCAmelCase             =       0
     __lowerCAmelCase             =       0
     __lowerCAmelCase             =       1

     # Calculating the hash of pattern and substring of text
     for i in range(__snake_case							):
          __lowerCAmelCase             =       (ord(pattern[i]							) + p_hash * alphabet_size) % modulus
          __lowerCAmelCase             =       (ord(text[i]							) + text_hash * alphabet_size) % modulus
          if i == p_len - 1:
               continue
          __lowerCAmelCase             =       (modulus_power * alphabet_size) % modulus

     for i in range(0       ,			t_len - p_len + 1							):
          if text_hash == p_hash and text[i : i + p_len] == pattern:
               return True
          if i == t_len - p_len:
               continue
          # Calculate the https://en.wikipedia.org/wiki/Rolling_hash
          __lowerCAmelCase             =       (
              (text_hash - ord(text[i]							) * modulus_power) * alphabet_size
              + ord(text[i + p_len]							)
          ) % modulus
     return False





def    __lowerCAmelCase   (    ):
     __lowerCAmelCase             =       "abc1abc12"
     __lowerCAmelCase             =       "alskfjaldsabc1abc1abc12k23adsfabcabc"
     __lowerCAmelCase             =       "alskfjaldsk23adsfabcabc"
     assert rabin_karp(__snake_case       ,			__snake_case							) and not rabin_karp(__snake_case       ,			__snake_case							)

     # Test 2)
     __lowerCAmelCase             =       "ABABX"
     __lowerCAmelCase             =       "ABABZABABYABABX"
     assert rabin_karp(__snake_case       ,			__snake_case							)

     # Test 3)
     __lowerCAmelCase             =       "AAAB"
     __lowerCAmelCase             =       "ABAAAAAB"
     assert rabin_karp(__snake_case       ,			__snake_case							)

     # Test 4)
     __lowerCAmelCase             =       "abcdabcy"
     __lowerCAmelCase             =       "abcxabcdabxabcdabcdabcy"
     assert rabin_karp(__snake_case       ,			__snake_case							)

     # Test 5)
     __lowerCAmelCase             =       "Lü"
     __lowerCAmelCase             =       "Lüsai"
     assert rabin_karp(__snake_case       ,			__snake_case							)
     __lowerCAmelCase             =       "Lue"
     assert not rabin_karp(__snake_case       ,			__snake_case							)
     print("Success."							)


if __name__ == "__main__":
 test_rabin_karp()








from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tokenizers_available, is_torch_available


__lowerCAmelCase					   =       {
    'configuration_bloom': ['BLOOM_PRETRAINED_CONFIG_ARCHIVE_MAP', 'BloomConfig', 'BloomOnnxConfig'],
}
try:
							if not is_tokenizers_available():
														raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
							pass
else:
							__lowerCAmelCase					   =       ['BloomTokenizerFast']

try:
							if not is_torch_available():
														raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
							pass
else:
							__lowerCAmelCase					   =       [
							    'BLOOM_PRETRAINED_MODEL_ARCHIVE_LIST',
							    'BloomForCausalLM',
							    'BloomModel',
							    'BloomPreTrainedModel',
							    'BloomForSequenceClassification',
							    'BloomForTokenClassification',
							    'BloomForQuestionAnswering',
							]

if TYPE_CHECKING:
							from .configuration_bloom import BLOOM_PRETRAINED_CONFIG_ARCHIVE_MAP, BloomConfig, BloomOnnxConfig

							try:
														if not is_tokenizers_available():
																					raise OptionalDependencyNotAvailable()
							except OptionalDependencyNotAvailable:
														pass
							else:
														from .tokenization_bloom_fast import BloomTokenizerFast

							try:
														if not is_torch_available():
																					raise OptionalDependencyNotAvailable()
							except OptionalDependencyNotAvailable:
														pass
							else:
														from .modeling_bloom import (
														    BLOOM_PRETRAINED_MODEL_ARCHIVE_LIST,
														    BloomForCausalLM,
														    BloomForQuestionAnswering,
														    BloomForSequenceClassification,
														    BloomForTokenClassification,
														    BloomModel,
														    BloomPreTrainedModel,
														)

else:
							import sys

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