



'''simple docstring'''





# 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 lowerCAmelCase						(__A						,			__A						,			__A						,			__A):



     """simple docstring"""



     _a											=						multiprocessing.Manager()
     _a											=						manager.list()

     _a											=						multiprocessing.Process(target=_A						,			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 lowerCAmelCase						(__A						,			__A						,			__A):



     """simple docstring"""



     with create_tempdir():
          # These system calls are needed when cleaning up tempdir.
          import os
          import shutil

          _a											=						shutil.rmtree
          _a											=						os.rmdir
          _a											=						os.chdir

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

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

          # Needed for cleaning up.
          _a											=						rmtree
          _a											=						rmdir
          _a											=						chdir




@contextlib.contextmanager
def lowerCAmelCase						(__A):



     """simple docstring"""



     def signal_handler(__A						,			__A):
          raise TimeoutException('''Timed out!''')

     signal.setitimer(signal.ITIMER_REAL						,			_A)
     signal.signal(signal.SIGALRM						,			_A)
     try:
          yield
     finally:
          signal.setitimer(signal.ITIMER_REAL						,			0)




@contextlib.contextmanager
def lowerCAmelCase						():



     """simple docstring"""



     _a											=						WriteOnlyStringIO()
     with contextlib.redirect_stdout(_A):
          with contextlib.redirect_stderr(_A):
               with redirect_stdin(_A):
                    yield




@contextlib.contextmanager
def lowerCAmelCase						():



     """simple docstring"""



     with tempfile.TemporaryDirectory() as dirname:
          with chdir(_A):
               yield dirname






class __A    (						lowerCAmelCase__		):



 '''simple docstring'''







 pass






class __A    (						io.StringIO		):



 '''simple docstring'''







 def       a__						(self				,     *A				,     **A )					->  Dict:


      """simple docstring"""



      raise OSError



 def       a__						(self				,     *A				,     **A )					->  Optional[int]:


      """simple docstring"""



      raise OSError



 def       a__						(self				,     *A				,     **A )					->  Tuple:


      """simple docstring"""



      raise OSError



 def       a__						(self				,     *A				,     **A )					->  Union[str, Any]:


      """simple docstring"""



      return False






class __A    (						contextlib._RedirectStream		):  # type: ignore



 '''simple docstring'''







 __lowerCamelCase					: List[Any]    = "stdin"





@contextlib.contextmanager
def lowerCAmelCase						(__A):



     """simple docstring"""



     if root == ".":
          yield
          return
     _a											=						os.getcwd()
     os.chdir(_A)
     try:
          yield
     except BaseException as exc:
          raise exc
     finally:
          os.chdir(_A)




def lowerCAmelCase						(__A=None):



     """simple docstring"""



     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

     _a											=						None
     _a											=						None

     import os

     _a											=						'''1'''

     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None

     import shutil

     _a											=						None
     _a											=						None
     _a											=						None

     import subprocess

     _a											=						None  # type: ignore

     _a											=						None

     import sys

     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None
     _a											=						None








'''simple docstring'''





lowercase_	 =						256
# Modulus to hash a string
lowercase_	 =						1_000_003




def lowerCAmelCase						(__A						,			__A):



     """simple docstring"""



     _a											=						len(__A)
     _a											=						len(__A)
     if p_len > t_len:
          return False

     _a											=						0
     _a											=						0
     _a											=						1

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




def lowerCAmelCase						():



     """simple docstring"""



     _a											=						'''abc1abc12'''
     _a											=						'''alskfjaldsabc1abc1abc12k23adsfabcabc'''
     _a											=						'''alskfjaldsk23adsfabcabc'''
     assert rabin_karp(__A						,			__A) and not rabin_karp(__A						,			__A)

     # Test 2)
     _a											=						'''ABABX'''
     _a											=						'''ABABZABABYABABX'''
     assert rabin_karp(__A						,			__A)

     # Test 3)
     _a											=						'''AAAB'''
     _a											=						'''ABAAAAAB'''
     assert rabin_karp(__A						,			__A)

     # Test 4)
     _a											=						'''abcdabcy'''
     _a											=						'''abcxabcdabxabcdabcdabcy'''
     assert rabin_karp(__A						,			__A)

     # Test 5)
     _a											=						'''Lü'''
     _a											=						'''Lüsai'''
     assert rabin_karp(__A						,			__A)
     _a											=						'''Lue'''
     assert not rabin_karp(__A						,			__A)
     print('''Success.''')


if __name__ == "__main__":
  test_rabin_karp()



