






from typing import Any
def      a_ (      _A      ,   _A      ,   _A      ,   _A      ,   _A      ,   )			->			list:







				"""simple docstring"""
				_validation(
				    _A      ,   _A      ,   _A      ,   _A      ,   _A      ,   )
				# Creates data structures and fill initial step
				snake_case__									=     {}
				snake_case__									=     {}
				for state in states_space:
								snake_case__									=     observations_space[0]
								snake_case__									=     (
								    initial_probabilities[state] * emission_probabilities[state][observation]
								)
								snake_case__									=     None

				# Fills the data structure with the probabilities of
				# different transitions and pointers to previous states
				for o in range(1      ,   len(_A  )  ):
								snake_case__									=     observations_space[o]
								snake_case__									=     observations_space[o - 1]
								for state in states_space:
												# Calculates the argmax for probability function
												snake_case__									=     ''
												snake_case__									=     -1
												for k_state in states_space:
																snake_case__									=     (
																    probabilities[(k_state, prior_observation)]
																    * transition_probabilities[k_state][state]
																    * emission_probabilities[state][observation]
																)
																if probability > max_probability:
																				snake_case__									=     probability
																				snake_case__									=     k_state

            # Update probabilities and pointers dicts
												snake_case__									=     (
												    probabilities[(arg_max, prior_observation)]
												    * transition_probabilities[arg_max][state]
												    * emission_probabilities[state][observation]
												)

												snake_case__									=     arg_max

    # The final observation
				snake_case__									=     observations_space[len(_A  ) - 1]

				# argmax for given final observation
				snake_case__									=     ''
				snake_case__									=     -1
				for k_state in states_space:
								snake_case__									=     probabilities[(k_state, final_observation)]
								if probability > max_probability:
												snake_case__									=     probability
												snake_case__									=     k_state
				snake_case__									=     arg_max

				# Process pointers backwards
				snake_case__									=     last_state
				snake_case__									=     []
				for o in range(len(_A  ) - 1      ,   -1      ,   -1  ):
								result.append(_A  )
								snake_case__									=     pointers[previous, observations_space[o]]
				result.reverse()

				return result
def      a_ (      _A      ,   _A      ,   _A      ,   _A      ,   _A      ,   )			->			None:







				"""simple docstring"""
				_validate_not_empty(
				    _A      ,   _A      ,   _A      ,   _A      ,   _A      ,   )
				_validate_lists(_A      ,   _A  )
				_validate_dicts(
				    _A      ,   _A      ,   _A  )
def      a_ (      _A      ,   _A      ,   _A      ,   _A      ,   _A      ,   )			->			None:







				"""simple docstring"""
				if not all(
				    [
				        observations_space,
				        states_space,
				        initial_probabilities,
				        transition_probabilities,
				        emission_probabilities,
				    ]  ):
								raise ValueError('There\'s an empty parameter'  )
def      a_ (      _A      ,   _A  )			->			None:







				"""simple docstring"""
				_validate_list(_A      ,   'observations_space'  )
				_validate_list(_A      ,   'states_space'  )
def      a_ (      _A      ,   _A  )			->			None:







				"""simple docstring"""
				if not isinstance(_object      ,   _A  ):
								snake_case__									=     f'''{var_name} must be a list'''
								raise ValueError(_A  )
				else:
								for x in _object:
												if not isinstance(_A      ,   _A  ):
																snake_case__									=     f'''{var_name} must be a list of strings'''
																raise ValueError(_A  )
def      a_ (      _A      ,   _A      ,   _A      ,   )			->			None:







				"""simple docstring"""
				_validate_dict(_A      ,   'initial_probabilities'      ,   _A  )
				_validate_nested_dict(_A      ,   'transition_probabilities'  )
				_validate_nested_dict(_A      ,   'emission_probabilities'  )
def      a_ (      _A      ,   _A  )			->			None:







				"""simple docstring"""
				_validate_dict(_object      ,   _A      ,   _A  )
				for x in _object.values():
								_validate_dict(_A      ,   _A      ,   _A      ,   _A  )
def      a_ (      _A      ,   _A      ,   _A      ,   _A = False  )			->			None:







				"""simple docstring"""
				if not isinstance(_object      ,   _A  ):
								snake_case__									=     f'''{var_name} must be a dict'''
								raise ValueError(_A  )
				if not all(isinstance(_A      ,   _A  ) for x in _object  ):
								snake_case__									=     f'''{var_name} all keys must be strings'''
								raise ValueError(_A  )
				if not all(isinstance(_A      ,   _A  ) for x in _object.values()  ):
								snake_case__									=     'nested dictionary ' if nested else ''
								snake_case__									=     f'''{var_name} {nested_text}all values must be {value_type.__name__}'''
								raise ValueError(_A  )


if __name__ == "__main__":
							from doctest import testmod

							testmod()












__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()




