





import inspect
import unittest

class    lowerCAmelCase							(					unittest.TestCase			):
 def      A_	(      self  :      List[Any]	)			->	Dict:
     try:
         import diffusers  # noqa: F401
     except ImportError:
         assert False







 def      A_	(      self  :      str	)			->	List[Any]:
     import diffusers
     from diffusers.dependency_versions_table import deps

     lowerCamelCase__    :      List[Any]					 =		inspect.getmembers(UpperCAmelCase			,     inspect.isclass	)

     for cls_name, cls_module in all_classes:
         if "dummy_" in cls_module.__module__:
             for backend in cls_module._backends:
                 if backend == "k_diffusion":
                     lowerCamelCase__    :      str					 =		'k-diffusion'
                 elif backend == "invisible_watermark":
                     lowerCamelCase__    :      Dict					 =		'invisible-watermark'
                 assert backend in deps, F"""{backend} is not in the deps table!"""







SCREAMING_SNAKE_CASE							:Any							 =				256
# Modulus to hash a string
SCREAMING_SNAKE_CASE							:Union[str, Any]							 =				100_0003


def 						UpperCAmelCase			(	a_		,   a_						)		->	bool:







				"""simple docstring"""



				__A   			= len(a_						)
				__A   			= len(a_						)
				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(a_						):
								__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 						UpperCAmelCase			(	)		->	None:







				"""simple docstring"""



				__A   			= "abc1abc12"
				__A   			= "alskfjaldsabc1abc1abc12k23adsfabcabc"
				__A   			= "alskfjaldsk23adsfabcabc"
				assert rabin_karp(a_		,   a_						) and not rabin_karp(a_		,   a_						)

				# Test 2)
				__A   			= "ABABX"
				__A   			= "ABABZABABYABABX"
				assert rabin_karp(a_		,   a_						)

				# Test 3)
				__A   			= "AAAB"
				__A   			= "ABAAAAAB"
				assert rabin_karp(a_		,   a_						)

				# Test 4)
				__A   			= "abcdabcy"
				__A   			= "abcxabcdabxabcdabcdabcy"
				assert rabin_karp(a_		,   a_						)

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


if __name__ == "__main__":
					test_rabin_karp()
