




class 			lowerCamelCase_				:


 '''simple docstring'''







 def __init__(				self    :						str		):
       SCREAMING_SNAKE_CASE_      		=     {}



 def  lowerCAmelCase_    (				self    :						List[str]		):
       print(self.vertex		)
       for i in self.vertex:
             print(_lowerCAmelCase							,							' -> '							,							' -> '.join([str(_lowerCAmelCase		) for j in self.vertex[i]]		)		)



 def  lowerCAmelCase_    (				self    :						Union[str, Any]							,							_lowerCAmelCase    :						int							,							_lowerCAmelCase    :						int		):
       # check if vertex is already present,
       if from_vertex in self.vertex:
             self.vertex[from_vertex].append(_lowerCAmelCase		)
       else:
             # else make a new vertex
             SCREAMING_SNAKE_CASE_      		=     [to_vertex]



 def  lowerCAmelCase_    (				self    :						Optional[Any]		):
       # visited array for storing already visited nodes
       SCREAMING_SNAKE_CASE_      		=     [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  lowerCAmelCase_    (				self    :						Tuple							,							_lowerCAmelCase    :						int							,							_lowerCAmelCase    :						list		):
       # mark start vertex as visited
       SCREAMING_SNAKE_CASE_      		=     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__					:  List[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
from __future__ import annotations


def 				lowerCAmelCase__       (			a__    ,     a__ )      ->bool:




  '''simple docstring'''

  _UpperCamelCase           =    get_failure_array(a__ )

  # 2) Step through text searching for pattern
  _UpperCamelCase      ,						_UpperCamelCase           =    0, 0  # index into text, pattern
  while i < len(a__ ):
    if pattern[j] == text[i]:
      if j == (len(a__ ) - 1):
        return True
      j += 1

    # if this is a prefix in our pattern
    # just go back far enough to continue
    elif j > 0:
      _UpperCamelCase           =    failure[j - 1]
      continue
    i += 1
  return False


def 				lowerCAmelCase__       (			a__ )      ->list[int]:




  '''simple docstring'''

  _UpperCamelCase           =    [0]
  _UpperCamelCase           =    0
  _UpperCamelCase           =    1
  while j < len(a__ ):
    if pattern[i] == pattern[j]:
      i += 1
    elif i > 0:
      _UpperCamelCase           =    failure[i - 1]
      continue
    j += 1
    failure.append(a__ )
  return failure


if __name__ == "__main__":
   # Test 1)
   lowerCamelCase__  =					'''abc1abc12'''
   lowerCamelCase__  =					'''alskfjaldsabc1abc1abc12k23adsfabcabc'''
   lowerCamelCase__  =					'''alskfjaldsk23adsfabcabc'''
   assert kmp(pattern, texta) and not kmp(pattern, texta)

   # Test 2)
   lowerCamelCase__  =					'''ABABX'''
   lowerCamelCase__  =					'''ABABZABABYABABX'''
   assert kmp(pattern, text)

   # Test 3)
   lowerCamelCase__  =					'''AAAB'''
   lowerCamelCase__  =					'''ABAAAAAB'''
   assert kmp(pattern, text)

   # Test 4)
   lowerCamelCase__  =					'''abcdabcy'''
   lowerCamelCase__  =					'''abcxabcdabxabcdabcdabcy'''
   assert kmp(pattern, text)

   # Test 5)
   lowerCamelCase__  =					'''aabaabaaa'''
   assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]




