





_snake_case  :   int						   =  256
# Modulus to hash a string
_snake_case  :   Any						   =  1000003

def   a_   (			lowerCAmelCase_				:      str,     lowerCAmelCase_				:      str     ):
   __lowerCAmelCase							     =     len(lowerCamelCase_     )
   __lowerCAmelCase							     =     len(lowerCamelCase_     )
   if p_len > t_len:
      return False

   __lowerCAmelCase							     =     0
   __lowerCAmelCase							     =     0
   __lowerCAmelCase							     =     1

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

def   a_   (			):
   __lowerCAmelCase							     =     """abc1abc12"""
   __lowerCAmelCase							     =     """alskfjaldsabc1abc1abc12k23adsfabcabc"""
   __lowerCAmelCase							     =     """alskfjaldsk23adsfabcabc"""
   assert rabin_karp(lowerCamelCase_,     lowerCamelCase_     ) and not rabin_karp(lowerCamelCase_,     lowerCamelCase_     )

   # Test 2)
   __lowerCAmelCase							     =     """ABABX"""
   __lowerCAmelCase							     =     """ABABZABABYABABX"""
   assert rabin_karp(lowerCamelCase_,     lowerCamelCase_     )

   # Test 3)
   __lowerCAmelCase							     =     """AAAB"""
   __lowerCAmelCase							     =     """ABAAAAAB"""
   assert rabin_karp(lowerCamelCase_,     lowerCamelCase_     )

   # Test 4)
   __lowerCAmelCase							     =     """abcdabcy"""
   __lowerCAmelCase							     =     """abcxabcdabxabcdabcdabcy"""
   assert rabin_karp(lowerCamelCase_,     lowerCamelCase_     )

   # Test 5)
   __lowerCAmelCase							     =     """Lü"""
   __lowerCAmelCase							     =     """Lüsai"""
   assert rabin_karp(lowerCamelCase_,     lowerCamelCase_     )
   __lowerCAmelCase							     =     """Lue"""
   assert not rabin_karp(lowerCamelCase_,     lowerCamelCase_     )
   print('Success.'     )


if __name__ == "__main__":
     test_rabin_karp()








class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		Union[str, Any] ,  lowerCAmelCase_			:		List[str] ,  lowerCAmelCase_			:		int ,  lowerCAmelCase_			:		Dict					)							->						List[str]:
     __lowerCAmelCase							     =     name
     __lowerCAmelCase							     =     value
     __lowerCAmelCase							     =     weight






  def __repr__(    self			:		Union[str, Any]					)							->						List[str]:
     return f"""{self.__class__.__name__}({self.name}, {self.value}, {self.weight})"""






  def     lowercase		(    self			:		int					)							->						Optional[int]:
     return self.value






  def     lowercase		(    self			:		Optional[Any]					)							->						Union[str, Any]:
     return self.name






  def     lowercase		(    self			:		List[Any]					)							->						Tuple:
     return self.weight






  def     lowercase		(    self			:		int					)							->						Dict:
     return self.value / self.weight





def   a_   (			lowerCAmelCase_				:      Dict,     lowerCAmelCase_				:      int,     lowerCAmelCase_				:      Optional[int]     ):
   __lowerCAmelCase							     =     []
   for i in range(len(lowerCAmelCase_     )     ):
      menu.append(Things(name[i],     value[i],     weight[i]     )     )
   return menu

def   a_   (			lowerCAmelCase_				:      Optional[int],     lowerCAmelCase_				:      List[Any],     lowerCAmelCase_				:      Optional[Any]     ):
   __lowerCAmelCase							     =     sorted(lowerCAmelCase_,     key=lowerCAmelCase_,     reverse=lowerCAmelCase_     )
   __lowerCAmelCase							     =     []
   __lowerCAmelCase     ,     __lowerCAmelCase							     =     0.0, 0.0
   for i in range(len(lowerCAmelCase_     )     ):
      if (total_cost + items_copy[i].get_weight()) <= max_cost:
         result.append(items_copy[i]     )
         total_cost += items_copy[i].get_weight()
         total_value += items_copy[i].get_value()
   return (result, total_value)

def   a_   (			):
   pass


if __name__ == "__main__":
     import doctest

     doctest.testmod()

