

"""simple docstring"""



SCREAMING_SNAKE_CASE_					:	Dict							  =						2_5_6
# Modulus to hash a string
SCREAMING_SNAKE_CASE_					:	Any							  =						1_0_0_0_0_0_3





def  _snake_case     (    UpperCAmelCase_  :					str					,   UpperCAmelCase_  :					str			):
     A__										=  len(UpperCAmelCase_			)
     A__										=  len(UpperCAmelCase_			)
     if p_len > t_len:
          return False

     A__										=  0
     A__										=  0
     A__										=  1

     # Calculating the hash of pattern and substring of text
     for i in range(UpperCAmelCase_			):
          A__										=  (ord(pattern[i]			) + p_hash * alphabet_size) % modulus
          A__										=  (ord(text[i]			) + text_hash * alphabet_size) % modulus
          if i == p_len - 1:
               continue
          A__										=  (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
          A__										=  (
              (text_hash - ord(text[i]			) * modulus_power) * alphabet_size
              + ord(text[i + p_len]			)
          ) % modulus
     return False





def  _snake_case     (    ):
     A__										=  """abc1abc12"""
     A__										=  """alskfjaldsabc1abc1abc12k23adsfabcabc"""
     A__										=  """alskfjaldsk23adsfabcabc"""
     assert rabin_karp(UpperCAmelCase_					,   UpperCAmelCase_			) and not rabin_karp(UpperCAmelCase_					,   UpperCAmelCase_			)

     # Test 2)
     A__										=  """ABABX"""
     A__										=  """ABABZABABYABABX"""
     assert rabin_karp(UpperCAmelCase_					,   UpperCAmelCase_			)

     # Test 3)
     A__										=  """AAAB"""
     A__										=  """ABAAAAAB"""
     assert rabin_karp(UpperCAmelCase_					,   UpperCAmelCase_			)

     # Test 4)
     A__										=  """abcdabcy"""
     A__										=  """abcxabcdabxabcdabcdabcy"""
     assert rabin_karp(UpperCAmelCase_					,   UpperCAmelCase_			)

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


if __name__ == "__main__":
 test_rabin_karp()









"""simple docstring"""



from itertools import count





def  _snake_case     (    UpperCAmelCase_  :					int = 50			):
     A__										=  [1] * min_block_length

     for n in count(UpperCAmelCase_			):
          fill_count_functions.append(1			)

          for block_length in range(UpperCAmelCase_					,   n + 1			):
               for block_start in range(n - block_length			):
                    fill_count_functions[n] += fill_count_functions[
                        n - block_start - block_length - 1
                    ]

               fill_count_functions[n] += 1

          if fill_count_functions[n] > 100_0000:
               break

     return n


if __name__ == "__main__":
 print(f"""{solution() = }""")






