


"""simple docstring"""


import heapq as hq
import math
from collections.abc import Iterator
class   _UpperCamelCase  :
							'''simple docstring'''







							def __init__(     self    ,   __a	):
										__lowerCAmelCase				    =			str(id_	)
										__lowerCAmelCase				    =			None
										__lowerCAmelCase				    =			None
										__lowerCAmelCase				    =			[]
										__lowerCAmelCase				    =			{}  # {vertex:distance}

							def __lt__(     self    ,   __a	):
										return self.key < other.key

							def __repr__(     self	):
										return self.id

							def 			snake_case				(     self    ,   __a	):
										self.neighbors.append(__a	)



							def 			snake_case				(     self    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			weight


def _lowerCamelCase	(		_UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase      ):

			'''simple docstring'''




			graph[a - 1].add_neighbor(graph[b - 1]      )
			graph[b - 1].add_neighbor(graph[a - 1]      )
			# add the edges:
			graph[a - 1].add_edge(graph[b - 1]    , _UpperCamelCase      )
			graph[b - 1].add_edge(graph[a - 1]    , _UpperCamelCase      )


def _lowerCamelCase	(		_UpperCamelCase    , _UpperCamelCase      ):

			'''simple docstring'''




			__lowerCAmelCase				    =			[]
			for u in graph:
						__lowerCAmelCase				    =			math.inf
						__lowerCAmelCase				    =			None
			__lowerCAmelCase				    =			0
			__lowerCAmelCase				    =			graph[:]
			while q:
						__lowerCAmelCase				    =			min(_UpperCamelCase      )
						q.remove(_UpperCamelCase      )
						for v in u.neighbors:
									if (v in q) and (u.edges[v.id] < v.key):
												__lowerCAmelCase				    =			u
												__lowerCAmelCase				    =			u.edges[v.id]
			for i in range(1    , len(_UpperCamelCase      )      ):
						a.append((int(graph[i].id      ) + 1, int(graph[i].pi.id      ) + 1)      )
			return a


def _lowerCamelCase	(		_UpperCamelCase    , _UpperCamelCase      ):

			'''simple docstring'''




			for u in graph:
						__lowerCAmelCase				    =			math.inf
						__lowerCAmelCase				    =			None
			__lowerCAmelCase				    =			0

			__lowerCAmelCase				    =			list(_UpperCamelCase      )
			hq.heapify(_UpperCamelCase      )

			while h:
						__lowerCAmelCase				    =			hq.heappop(_UpperCamelCase      )
						for v in u.neighbors:
									if (v in h) and (u.edges[v.id] < v.key):
												__lowerCAmelCase				    =			u
												__lowerCAmelCase				    =			u.edges[v.id]
												hq.heapify(_UpperCamelCase      )

			for i in range(1    , len(_UpperCamelCase      )      ):
						yield (int(graph[i].id      ) + 1, int(graph[i].pi.id      ) + 1)


def _lowerCamelCase	(		):

			'''simple docstring'''






if __name__ == "__main__":
	import doctest

	doctest.testmod()











'''simple docstring'''


lowerCAmelCase					:     Optional[int]												=256
# Modulus to hash a string
lowerCAmelCase					:     Tuple												=1_000_003
def 							UpperCAmelCase_  (						__lowerCamelCase					:					str	,__lowerCamelCase					:					str ):
   lowercase_			:Dict    			= len(__lowerCamelCase )
   lowercase_			:int    			= len(__lowerCamelCase )
   if p_len > t_len:
      return False

   lowercase_			:Any    			= 0
   lowercase_			:Dict    			= 0
   lowercase_			:int    			= 1

   # Calculating the hash of pattern and substring of text
   for i in range(__lowerCamelCase ):
      lowercase_			:Union[str, Any]    			= (ord(pattern[i] ) + p_hash * alphabet_size) % modulus
      lowercase_			:Tuple    			= (ord(text[i] ) + text_hash * alphabet_size) % modulus
      if i == p_len - 1:
         continue
      lowercase_			:Tuple    			= (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
      lowercase_			:Tuple    			= (
          (text_hash - ord(text[i] ) * modulus_power) * alphabet_size
          + ord(text[i + p_len] )
      ) % modulus
   return False
def 							UpperCAmelCase_  (						):
   lowercase_			:List[Any]    			= "abc1abc12"
   lowercase_			:List[str]    			= "alskfjaldsabc1abc1abc12k23adsfabcabc"
   lowercase_			:int    			= "alskfjaldsk23adsfabcabc"
   assert rabin_karp(__lowerCamelCase	,__lowerCamelCase ) and not rabin_karp(__lowerCamelCase	,__lowerCamelCase )

   # Test 2)
   lowercase_			:Union[str, Any]    			= "ABABX"
   lowercase_			:Optional[Any]    			= "ABABZABABYABABX"
   assert rabin_karp(__lowerCamelCase	,__lowerCamelCase )

   # Test 3)
   lowercase_			:Dict    			= "AAAB"
   lowercase_			:int    			= "ABAAAAAB"
   assert rabin_karp(__lowerCamelCase	,__lowerCamelCase )

   # Test 4)
   lowercase_			:Tuple    			= "abcdabcy"
   lowercase_			:Union[str, Any]    			= "abcxabcdabxabcdabcdabcy"
   assert rabin_karp(__lowerCamelCase	,__lowerCamelCase )

   # Test 5)
   lowercase_			:Tuple    			= "Lü"
   lowercase_			:List[Any]    			= "Lüsai"
   assert rabin_karp(__lowerCamelCase	,__lowerCamelCase )
   lowercase_			:str    			= "Lue"
   assert not rabin_karp(__lowerCamelCase	,__lowerCamelCase )
   print("Success." )


if __name__ == "__main__":
 test_rabin_karp()


