





'''simple docstring'''
a__							:							List[Any] ={0: [2, 3], 1: [0], 2: [1], 3: [4], 4: []}

a__							:							Optional[int] ={0: [1, 2, 3], 1: [2], 2: [0], 3: [4], 4: [5], 5: [3]}
def 				lowercase__   (   __lowercase						:  dict[int, list[int]]				,  __lowercase						:  int				,  __lowercase						:  list[bool]     ) ->      list[int]:



       """simple docstring"""






       __UpperCamelCase       =  True
       __UpperCamelCase       =  []

       for neighbour in graph[vert]:
              if not visited[neighbour]:
                     order += topology_sort(__lowercase				,  __lowercase				,  __lowercase     )

       order.append(__lowercase     )

       return order
def 				lowercase__   (   __lowercase						:  dict[int, list[int]]				,  __lowercase						:  int				,  __lowercase						:  list[bool]     ) ->      list[int]:



       """simple docstring"""






       __UpperCamelCase       =  True
       __UpperCamelCase       =  [vert]

       for neighbour in reversed_graph[vert]:
              if not visited[neighbour]:
                     component += find_components(__lowercase				,  __lowercase				,  __lowercase     )

       return component


def 				lowercase__   (   __lowercase						:  dict[int, list[int]]     ) ->      list[list[int]]:



       """simple docstring"""






       __UpperCamelCase       =  len(__lowercase     ) * [False]
       __UpperCamelCase       =  {vert: [] for vert in range(len(__lowercase     )     )}

       for vert, neighbours in graph.items():
              for neighbour in neighbours:
                     reversed_graph[neighbour].append(__lowercase     )

       __UpperCamelCase       =  []
       for i, was_visited in enumerate(__lowercase     ):
              if not was_visited:
                     order += topology_sort(__lowercase				,  __lowercase				,  __lowercase     )

       __UpperCamelCase       =  []
       __UpperCamelCase       =  len(__lowercase     ) * [False]

       for i in range(len(__lowercase     )     ):
              __UpperCamelCase       =  order[len(__lowercase     ) - i - 1]
              if not visited[vert]:
                     __UpperCamelCase       =  find_components(__lowercase				,  __lowercase				,  __lowercase     )
                     components_list.append(__lowercase     )

       return components_list







'''simple docstring'''
a__							:							Optional[Any] =256
# Modulus to hash a string
a__							:							Dict =1_000_003
def 				lowercase__   (   __lowercase						:  str				,  __lowercase						:  str     ) ->      bool:



       """simple docstring"""






       __UpperCamelCase       =  len(__lowercase     )
       __UpperCamelCase       =  len(__lowercase     )
       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(__lowercase     ):
              __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 				lowercase__   (   ) ->      None:



       """simple docstring"""






       __UpperCamelCase       =  'abc1abc12'
       __UpperCamelCase       =  'alskfjaldsabc1abc1abc12k23adsfabcabc'
       __UpperCamelCase       =  'alskfjaldsk23adsfabcabc'
       assert rabin_karp(__lowercase				,  __lowercase     ) and not rabin_karp(__lowercase				,  __lowercase     )

       # Test 2)
       __UpperCamelCase       =  'ABABX'
       __UpperCamelCase       =  'ABABZABABYABABX'
       assert rabin_karp(__lowercase				,  __lowercase     )

       # Test 3)
       __UpperCamelCase       =  'AAAB'
       __UpperCamelCase       =  'ABAAAAAB'
       assert rabin_karp(__lowercase				,  __lowercase     )

       # Test 4)
       __UpperCamelCase       =  'abcdabcy'
       __UpperCamelCase       =  'abcxabcdabxabcdabcdabcy'
       assert rabin_karp(__lowercase				,  __lowercase     )

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


if __name__ == "__main__":
    test_rabin_karp()
