
from __future__ import annotations

from typing import Any






class   UpperCAmelCase		:



   def __init__(self		:					str    ,						snake_case__		:					int )		->	None:


          '''simple docstring'''


          snake_case       :   str							=      num_of_nodes
          snake_case       :   list[list[int]]							=      []
          snake_case       :   dict[int, int]							=      {}



   def 				_SCREAMING_SNAKE_CASE   (self		:					Dict    ,						snake_case__		:					int    ,						snake_case__		:					int    ,						snake_case__		:					int )		->	None:


          '''simple docstring'''


          self.m_edges.append([u_node, v_node, weight] )



   def 				_SCREAMING_SNAKE_CASE   (self		:					List[Any]    ,						snake_case__		:					int )		->	int:


          '''simple docstring'''


          if self.m_component[u_node] == u_node:
                 return u_node
          return self.find_component(self.m_component[u_node] )



   def 				_SCREAMING_SNAKE_CASE   (self		:					List[str]    ,						snake_case__		:					int )		->	None:


          '''simple docstring'''


          if self.m_component[u_node] != u_node:
                 for k in self.m_component:
                        snake_case       :   Union[str, Any]							=      self.find_component(snake_case__ )



   def 				_SCREAMING_SNAKE_CASE   (self		:					str    ,						snake_case__		:					list[int]    ,						snake_case__		:					int    ,						snake_case__		:					int )		->	None:


          '''simple docstring'''


          if component_size[u_node] <= component_size[v_node]:
                 snake_case       :   Any							=      v_node
                 component_size[v_node] += component_size[u_node]
                 self.set_component(snake_case__ )

          elif component_size[u_node] >= component_size[v_node]:
                 snake_case       :   List[Any]							=      self.find_component(snake_case__ )
                 component_size[u_node] += component_size[v_node]
                 self.set_component(snake_case__ )



   def 				_SCREAMING_SNAKE_CASE   (self		:					Optional[Any] )		->	None:


          '''simple docstring'''


          snake_case       :   Dict							=      []
          snake_case       :   Any							=      0

          snake_case       :   list[Any]							=      [-1] * self.m_num_of_nodes

          # A list of components (initialized to all of the nodes)
          for node in range(self.m_num_of_nodes ):
                 self.m_component.update({node: node} )
                 component_size.append(1 )

          snake_case       :   str							=      self.m_num_of_nodes

          while num_of_components > 1:
                 for edge in self.m_edges:
                        snake_case				,					snake_case				,					snake_case       :   Dict							=      edge

                        snake_case       :   List[str]							=      self.m_component[u]
                        snake_case       :   Union[str, Any]							=      self.m_component[v]

                        if u_component != v_component:

                               for component in (u_component, v_component):
                                      if (
                                          minimum_weight_edge[component] == -1
                                          or minimum_weight_edge[component][2] > w
                                      ):
                                             snake_case       :   Optional[Any]							=      [u, v, w]

                 for edge in minimum_weight_edge:
                        if isinstance(snake_case__    ,						snake_case__ ):
                               snake_case				,					snake_case				,					snake_case       :   List[str]							=      edge

                               snake_case       :   Tuple							=      self.m_component[u]
                               snake_case       :   Dict							=      self.m_component[v]

                               if u_component != v_component:
                                      mst_weight += w
                                      self.union(snake_case__    ,						snake_case__    ,						snake_case__ )
                                      print(f"""Added edge [{u} - {v}]\nAdded weight: {w}\n""" )
                                      num_of_components -= 1

                 snake_case       :   Any							=      [-1] * self.m_num_of_nodes
          print(f"""The total weight of the minimal spanning tree is: {mst_weight}""" )



def 			UpperCamelCase					(    ):
       pass


if __name__ == "__main__":
   import doctest

   doctest.testmod()









'''simple docstring'''







from __future__ import annotations







class A__       :






      def __init__( self			:Union[str, Any]     ,						SCREAMING_SNAKE_CASE			:str     ,						SCREAMING_SNAKE_CASE			:str	)       ->					Optional[int]:




             '''simple docstring'''
             _a					,    _a    : List[str]     					=text, pattern
             _a					,    _a    : Union[str, Any]     					=len(SCREAMING_SNAKE_CASE	), len(SCREAMING_SNAKE_CASE	)






      def __UpperCAmelCase       ( self			:Optional[int]     ,						SCREAMING_SNAKE_CASE			:str	)       ->					int:




             '''simple docstring'''

             for i in range(self.patLen - 1     ,						-1     ,						-1	):
                    if char == self.pattern[i]:
                           return i
             return -1






      def __UpperCAmelCase       ( self			:Union[str, Any]     ,						SCREAMING_SNAKE_CASE			:int	)       ->					int:




             '''simple docstring'''

             for i in range(self.patLen - 1     ,						-1     ,						-1	):
                    if self.pattern[i] != self.text[current_pos + i]:
                           return current_pos + i
             return -1






      def __UpperCAmelCase       ( self			:Union[str, Any]	)       ->					list[int]:




             '''simple docstring'''
             # searches pattern in text and returns index positions
             _a    : Union[str, Any]     					=[]
             for i in range(self.textLen - self.patLen + 1	):
                    _a    : Any     					=self.mismatch_in_text(SCREAMING_SNAKE_CASE	)
                    if mismatch_index == -1:
                           positions.append(SCREAMING_SNAKE_CASE	)
                    else:
                           _a    : int     					=self.match_in_pattern(self.text[mismatch_index]	)
                           _a    : List[str]     					=(
                               mismatch_index - match_index
                           )  # shifting index lgtm [py/multiple-definition]
             return positions

A__:    Any					    =       '''ABAABA'''
A__:    int					    =       '''AB'''
A__:    Optional[int]					    =       BoyerMooreSearch(text, pattern)
A__:    Optional[Any]					    =       bms.bad_character_heuristic()

if len(positions) == 0:
   print('''No match found''')
else:
   print('''Pattern found in following positions: ''')
   print(positions)


