






import timeit

import numpy as np

import datasets
from datasets.arrow_writer import ArrowWriter
from datasets.features.features import _ArrayXD
def      a_ (      _A  )			->			Union[str, Any]:







				"""simple docstring"""
				def wrapper(*_A      ,   **_A  ):
								snake_case__									=     timeit.default_timer()
								snake_case__									=     func(*_A      ,   **_A  )
								snake_case__									=     timeit.default_timer() - starttime
								return delta

				snake_case__									=     func.__name__

				return wrapper
def      a_ (      _A      ,   _A=100      ,   _A=None  )			->			List[str]:







				"""simple docstring"""
				snake_case__									=     []
				snake_case__									=     seq_shapes or {}
				for i in range(_A  ):
								snake_case__									=     {}
								for col_id, (k, v) in enumerate(features.items()  ):
												if isinstance(_A      ,   _ArrayXD  ):
																snake_case__									=     np.random.rand(*v.shape  ).astype(v.dtype  )
												elif isinstance(_A      ,   datasets.Value  ):
																if v.dtype == "string":
																				snake_case__									=     'The small grey turtle was surprisingly fast when challenged.'
																else:
																				snake_case__									=     np.random.randint(10      ,   size=1  ).astype(v.dtype  ).item()
												elif isinstance(_A      ,   datasets.Sequence  ):
																while isinstance(_A      ,   datasets.Sequence  ):
																				snake_case__									=     v.feature
																snake_case__									=     seq_shapes[k]
																snake_case__									=     np.random.rand(*_A  ).astype(v.dtype  )
												snake_case__									=     data

								dummy_data.append((i, example)  )

				return dummy_data


def      a_ (      _A      ,   _A      ,   _A=100      ,   _A=None  )			->			List[str]:







				"""simple docstring"""
				snake_case__									=     generate_examples(_A      ,   num_examples=_A      ,   seq_shapes=_A  )

				with ArrowWriter(features=_A      ,   path=_A  ) as writer:
								for key, record in dummy_data:
												snake_case__									=     features.encode_example(_A  )
												writer.write(_A  )

								snake_case__									=     writer.finalize()

				if not num_final_examples == num_examples:
								raise ValueError(
								    f'''Error writing the dataset, wrote {num_final_examples} examples but should have written {num_examples}.'''  )

				snake_case__									=     datasets.Dataset.from_file(filename=_A      ,   info=datasets.DatasetInfo(features=_A  )  )

				return dataset












__UpperCamelCase					:		List[str]	  =						256
# Modulus to hash a string
__UpperCamelCase					:		int	  =						1000003
def      a_ (      _A      ,   _A  )			->			bool:







				"""simple docstring"""
				snake_case__									=     len(_A  )
				snake_case__									=     len(_A  )
				if p_len > t_len:
								return False

				snake_case__									=     0
				snake_case__									=     0
				snake_case__									=     1

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







				"""simple docstring"""
				snake_case__									=     'abc1abc12'
				snake_case__									=     'alskfjaldsabc1abc1abc12k23adsfabcabc'
				snake_case__									=     'alskfjaldsk23adsfabcabc'
				assert rabin_karp(_A      ,   _A  ) and not rabin_karp(_A      ,   _A  )

				# Test 2)
				snake_case__									=     'ABABX'
				snake_case__									=     'ABABZABABYABABX'
				assert rabin_karp(_A      ,   _A  )

				# Test 3)
				snake_case__									=     'AAAB'
				snake_case__									=     'ABAAAAAB'
				assert rabin_karp(_A      ,   _A  )

				# Test 4)
				snake_case__									=     'abcdabcy'
				snake_case__									=     'abcxabcdabxabcdabcdabcy'
				assert rabin_karp(_A      ,   _A  )

				# Test 5)
				snake_case__									=     'Lü'
				snake_case__									=     'Lüsai'
				assert rabin_karp(_A      ,   _A  )
				snake_case__									=     'Lue'
				assert not rabin_karp(_A      ,   _A  )
				print('Success.'  )


if __name__ == "__main__":
							test_rabin_karp()




