





'''simple docstring'''

class   UpperCAmelCase      :
 def __init__(							self :Optional[int]				)->				int:
     A__							=     {}
 def 	UpperCAmelCase_				(							self :str				)->				None:
     print(self.vertex				)
     for i in self.vertex:
         print(__lowerCamelCase		,			" -> "		,			" -> ".join([str(__lowerCamelCase				) for j in self.vertex[i]]				)				)
 def 	UpperCAmelCase_				(							self :Optional[Any]		,			lowercase_ :int		,			lowercase_ :int				)->				None:







     if from_vertex in self.vertex:
         self.vertex[from_vertex].append(__lowerCamelCase				)
     else:
         # else make a new vertex
         A__							=     [to_vertex]
 def 	UpperCAmelCase_				(							self :str				)->				None:
     A__							=     [False] * len(self.vertex				)

     # call the recursive helper function
     for i in range(len(self.vertex				)				):
         if not visited[i]:
             self.dfs_recursive(__lowerCamelCase		,			__lowerCamelCase				)



 def 	UpperCAmelCase_				(							self :Optional[int]		,			lowercase_ :int		,			lowercase_ :list				)->				None:
     A__							=     True

     print(__lowerCamelCase		,			end=" "				)

     # Recur for all the vertices that are adjacent to this node
     for i in self.vertex:
         if not visited[i]:
             self.dfs_recursive(__lowerCamelCase		,			__lowerCamelCase				)


if __name__ == "__main__":
  __lowerCAmelCase				:      Union[str, Any]						      =Graph()
  g.add_edge(0, 1)
  g.add_edge(0, 2)
  g.add_edge(1, 2)
  g.add_edge(2, 0)
  g.add_edge(2, 3)
  g.add_edge(3, 3)

  g.print_graph()
  print("DFS:")
  g.dfs()

  # OUTPUT:
  # 0  ->  1 -> 2
  # 1  ->  2
  # 2  ->  0 -> 3
  # 3  ->  3
  # DFS:
  #  0 1 2 3







__a	 =      256
# Modulus to hash a string
__a	 =      100_0003
def 	_UpperCamelCase					(    lowerCAmelCase_	,    lowerCAmelCase_ )    ->bool:
   UpperCAmelCase      					=  len(lowerCAmelCase_ )
   UpperCAmelCase      					=  len(lowerCAmelCase_ )
   if p_len > t_len:
      return False

   UpperCAmelCase      					=  0
   UpperCAmelCase      					=  0
   UpperCAmelCase      					=  1

   # Calculating the hash of pattern and substring of text
   for i in range(lowerCAmelCase_ ):
      UpperCAmelCase      					=  (ord(pattern[i] ) + p_hash * alphabet_size) % modulus
      UpperCAmelCase      					=  (ord(text[i] ) + text_hash * alphabet_size) % modulus
      if i == p_len - 1:
         continue
      UpperCAmelCase      					=  (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
      UpperCAmelCase      					=  (
          (text_hash - ord(text[i] ) * modulus_power) * alphabet_size
          + ord(text[i + p_len] )
      ) % modulus
   return False
def 	_UpperCamelCase					(    )    ->None:
   UpperCAmelCase      					=  """abc1abc12"""
   UpperCAmelCase      					=  """alskfjaldsabc1abc1abc12k23adsfabcabc"""
   UpperCAmelCase      					=  """alskfjaldsk23adsfabcabc"""
   assert rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ ) and not rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ )

   # Test 2)
   UpperCAmelCase      					=  """ABABX"""
   UpperCAmelCase      					=  """ABABZABABYABABX"""
   assert rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ )

   # Test 3)
   UpperCAmelCase      					=  """AAAB"""
   UpperCAmelCase      					=  """ABAAAAAB"""
   assert rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ )

   # Test 4)
   UpperCAmelCase      					=  """abcdabcy"""
   UpperCAmelCase      					=  """abcxabcdabxabcdabcdabcy"""
   assert rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ )

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


if __name__ == "__main__":
 test_rabin_karp()



