


# This code is adapted from OpenAI's release
# https://github.com/openai/human-eval/blob/master/human_eval/execution.py

import contextlib
import faulthandler
import io
import multiprocessing
import os
import platform
import signal
import tempfile
def 	_UpperCamelCase					(    lowerCAmelCase_	,    lowerCAmelCase_	,    lowerCAmelCase_	,    lowerCAmelCase_ )    ->Union[str, Any]:
   UpperCAmelCase      					=  multiprocessing.Manager()
   UpperCAmelCase      					=  manager.list()

   UpperCAmelCase      					=  multiprocessing.Process(target=lowerCAmelCase_	,    args=(check_program, result, timeout) )
   p.start()
   p.join(timeout=timeout + 1 )
   if p.is_alive():
      p.kill()

   if not result:
      result.append("""timed out""" )

   return {
       "task_id": task_id,
       "passed": result[0] == "passed",
       "result": result[0],
       "completion_id": completion_id,
   }
def 	_UpperCamelCase					(    lowerCAmelCase_	,    lowerCAmelCase_	,    lowerCAmelCase_ )    ->int:
   with create_tempdir():
      # These system calls are needed when cleaning up tempdir.
      import os
      import shutil

      UpperCAmelCase      					=  shutil.rmtree
      UpperCAmelCase      					=  os.rmdir
      UpperCAmelCase      					=  os.chdir

      # Disable functionalities that can make destructive changes to the test.
      reliability_guard()

      # Run program.
      try:
         UpperCAmelCase      					=  {}
         with swallow_io():
            with time_limit(lowerCAmelCase_ ):
               exec(lowerCAmelCase_	,    lowerCAmelCase_ )
         result.append("""passed""" )
      except TimeoutException:
         result.append("""timed out""" )
      except BaseException as e:
         result.append(F"""failed: {e}""" )

      # Needed for cleaning up.
      UpperCAmelCase      					=  rmtree
      UpperCAmelCase      					=  rmdir
      UpperCAmelCase      					=  chdir
@contextlib.contextmanager
def 	_UpperCamelCase					(    lowerCAmelCase_ )    ->Optional[int]:
   def signal_handler(lowerCAmelCase_	,    lowerCAmelCase_ ):
      raise TimeoutException("""Timed out!""" )

   signal.setitimer(signal.ITIMER_REAL	,    lowerCAmelCase_ )
   signal.signal(signal.SIGALRM	,    lowerCAmelCase_ )
   try:
      yield
   finally:
      signal.setitimer(signal.ITIMER_REAL	,    0 )
@contextlib.contextmanager
def 	_UpperCamelCase					(    )    ->Any:
   UpperCAmelCase      					=  WriteOnlyStringIO()
   with contextlib.redirect_stdout(lowerCAmelCase_ ):
      with contextlib.redirect_stderr(lowerCAmelCase_ ):
         with redirect_stdin(lowerCAmelCase_ ):
            yield
@contextlib.contextmanager
def 	_UpperCamelCase					(    )    ->Optional[int]:
   with tempfile.TemporaryDirectory() as dirname:
      with chdir(lowerCAmelCase_ ):
         yield dirname






class 	__lowercase					(	__snake_case	):
      pass






class 	__lowercase					(	io.StringIO	):





      def 							_lowercase					(		self    :       Tuple       ,							*__lowerCamelCase    :       Dict       ,							**__lowerCamelCase    :       Optional[int]							)     -> int:






         """simple docstring"""







         raise OSError





      def 							_lowercase					(		self    :       List[Any]       ,							*__lowerCamelCase    :       Any       ,							**__lowerCamelCase    :       Optional[Any]							)     -> List[str]:






         """simple docstring"""







         raise OSError





      def 							_lowercase					(		self    :       Any       ,							*__lowerCamelCase    :       Any       ,							**__lowerCamelCase    :       Any							)     -> Optional[int]:






         """simple docstring"""







         raise OSError





      def 							_lowercase					(		self    :       Optional[int]       ,							*__lowerCamelCase    :       List[str]       ,							**__lowerCamelCase    :       str							)     -> Optional[int]:






         """simple docstring"""







         return False






class 	__lowercase					(	contextlib._RedirectStream	):  # type: ignore
      UpperCamelCase										=							'''stdin'''

@contextlib.contextmanager
def 	_UpperCamelCase					(    lowerCAmelCase_ )    ->int:
   if root == ".":
      yield
      return
   UpperCAmelCase      					=  os.getcwd()
   os.chdir(lowerCAmelCase_ )
   try:
      yield
   except BaseException as exc:
      raise exc
   finally:
      os.chdir(lowerCAmelCase_ )







def 	_UpperCamelCase					(    lowerCAmelCase_=None )    ->str:

   if maximum_memory_bytes is not None:
      import resource

      resource.setrlimit(resource.RLIMIT_AS	,    (maximum_memory_bytes, maximum_memory_bytes) )
      resource.setrlimit(resource.RLIMIT_DATA	,    (maximum_memory_bytes, maximum_memory_bytes) )
      if not platform.uname().system == "Darwin":
         resource.setrlimit(resource.RLIMIT_STACK	,    (maximum_memory_bytes, maximum_memory_bytes) )

   faulthandler.disable()

   import builtins

   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None

   import os

   UpperCAmelCase      					=  """1"""

   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None

   import shutil

   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None

   import subprocess

   UpperCAmelCase      					=  None  # type: ignore

   UpperCAmelCase      					=  None

   import sys

   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None
   UpperCAmelCase      					=  None







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



