


'''simple docstring'''

class 						__SCREAMING_SNAKE_CASE					:






     def __init__(			self     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    Optional[int]:
          _a						=		None
          _a						=		None
          _a						=		graph

          self._normalize_graph(__UpperCamelCase     ,							__UpperCamelCase		)
          _a						=		len(__UpperCamelCase		)
          _a						=		None






     def  a_					(			self     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    Any:
          if sources is int:
               _a						=		[sources]
          if sinks is int:
               _a						=		[sinks]

          if len(__UpperCamelCase		) == 0 or len(__UpperCamelCase		) == 0:
               return

          _a						=		sources[0]
          _a						=		sinks[0]

          # make fake vertex if there are more
          # than one source or sink
          if len(__UpperCamelCase		) > 1 or len(__UpperCamelCase		) > 1:
               _a						=		0
               for i in sources:
                    max_input_flow += sum(self.graph[i]		)

               _a						=		len(self.graph		) + 1
               for room in self.graph:
                    room.insert(0     ,							0		)
               self.graph.insert(0     ,							[0] * size		)
               for i in sources:
                    _a						=		max_input_flow
               _a						=		0

               _a						=		len(self.graph		) + 1
               for room in self.graph:
                    room.append(0		)
               self.graph.append([0] * size		)
               for i in sinks:
                    _a						=		max_input_flow
               _a						=		size - 1






     def  a_					(			self		)       ->    Optional[Any]:
          if self.maximum_flow_algorithm is None:
               raise Exception("You need to set maximum flow algorithm before."		)
          if self.source_index is None or self.sink_index is None:
               return 0

          self.maximum_flow_algorithm.execute()
          return self.maximum_flow_algorithm.getMaximumFlow()






     def  a_					(			self     ,							__UpperCamelCase		)       ->    Optional[int]:
          _a						=		algorithm(self		)







class 						__SCREAMING_SNAKE_CASE					:






     def __init__(			self     ,							__UpperCamelCase		)       ->    List[str]:
          _a						=		flow_network
          _a						=		flow_network.verticesCount
          _a						=		flow_network.sourceIndex
          _a						=		flow_network.sinkIndex
          # it's just a reference, so you shouldn't change
          # it in your algorithms, use deep copy before doing that
          _a						=		flow_network.graph
          _a						=		False






     def  a_					(			self		)       ->    Any:
          if not self.executed:
               self._algorithm()
               _a						=		True






     def  a_					(			self		)       ->    Optional[int]:
          pass







class 						__SCREAMING_SNAKE_CASE					(      lowerCamelCase__ ):






     def __init__(			self     ,							__UpperCamelCase		)       ->    Tuple:
          super().__init__(__UpperCamelCase		)
          # use this to save your result
          _a						=		-1






     def  a_					(			self		)       ->    Optional[int]:
          if not self.executed:
               raise Exception("You should execute algorithm before using its result!"		)

          return self.maximum_flow







class 						__SCREAMING_SNAKE_CASE					(      lowerCamelCase__ ):






     def __init__(			self     ,							__UpperCamelCase		)       ->    int:
          super().__init__(__UpperCamelCase		)

          _a						=		[[0] * self.verticies_count for i in range(self.verticies_count		)]

          _a						=		[0] * self.verticies_count
          _a						=		[0] * self.verticies_count






     def  a_					(			self		)       ->    List[Any]:
          _a						=		self.verticies_count

          # push some substance to graph
          for nextvertex_index, bandwidth in enumerate(self.graph[self.source_index]		):
               self.preflow[self.source_index][nextvertex_index] += bandwidth
               self.preflow[nextvertex_index][self.source_index] -= bandwidth
               self.excesses[nextvertex_index] += bandwidth

          # Relabel-to-front selection rule
          _a						=		[
              i
              for i in range(self.verticies_count		)
              if i != self.source_index and i != self.sink_index
          ]

          # move through list
          _a						=		0
          while i < len(__UpperCamelCase		):
               _a						=		vertices_list[i]
               _a						=		self.heights[vertex_index]
               self.process_vertex(__UpperCamelCase		)
               if self.heights[vertex_index] > previous_height:
                    # if it was relabeled, swap elements
                    # and start from 0 index
                    vertices_list.insert(0     ,							vertices_list.pop(__UpperCamelCase		)		)
                    _a						=		0
               else:
                    i += 1

          _a						=		sum(self.preflow[self.source_index]		)






     def  a_					(			self     ,							__UpperCamelCase		)       ->    Tuple:
          while self.excesses[vertex_index] > 0:
               for neighbour_index in range(self.verticies_count		):
                    # if it's neighbour and current vertex is higher
                    if (
                        self.graph[vertex_index][neighbour_index]
                        - self.preflow[vertex_index][neighbour_index]
                        > 0
                        and self.heights[vertex_index] > self.heights[neighbour_index]
                    ):
                         self.push(__UpperCamelCase     ,							__UpperCamelCase		)

               self.relabel(__UpperCamelCase		)






     def  a_					(			self     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    Optional[int]:
          _a						=		min(
              self.excesses[from_index]     ,							self.graph[from_index][to_index] - self.preflow[from_index][to_index]     ,							)
          self.preflow[from_index][to_index] += preflow_delta
          self.preflow[to_index][from_index] -= preflow_delta
          self.excesses[from_index] -= preflow_delta
          self.excesses[to_index] += preflow_delta






     def  a_					(			self     ,							__UpperCamelCase		)       ->    Dict:
          _a						=		None
          for to_index in range(self.verticies_count		):
               if (
                   self.graph[vertex_index][to_index]
                   - self.preflow[vertex_index][to_index]
                   > 0
               ) and (min_height is None or self.heights[to_index] < min_height):
                    _a						=		self.heights[to_index]

          if min_height is not None:
               _a						=		min_height + 1


if __name__ == "__main__":
   lowercase__				     =		[0]
   lowercase__				     =		[3]
   # graph = [
   #     [0, 0, 4, 6, 0, 0],
   #     [0, 0, 5, 2, 0, 0],
   #     [0, 0, 0, 0, 4, 4],
   #     [0, 0, 0, 0, 6, 6],
   #     [0, 0, 0, 0, 0, 0],
   #     [0, 0, 0, 0, 0, 0],
   # ]
   lowercase__				     =		[[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]

   # prepare our network
   lowercase__				     =		FlowNetwork(graph, entrances, exits)
   # set algorithm
   flow_network.set_maximum_flow_algorithm(PushRelabelExecutor)
   # and calculate
   lowercase__				     =		flow_network.find_maximum_flow()

   print(f'''maximum flow is {maximum_flow}''')





'''simple docstring'''

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






def __UpperCamelCase   (			__lowerCamelCase		: str      ,  __lowerCamelCase		: str				)      ->     bool:







     '''simple docstring'''






     _a						=		len(__lowerCamelCase				)
     _a						=		len(__lowerCamelCase				)
     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(__lowerCamelCase				):
          _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 __UpperCamelCase   (			)      ->     None:







     '''simple docstring'''






     _a						=		"abc1abc12"
     _a						=		"alskfjaldsabc1abc1abc12k23adsfabcabc"
     _a						=		"alskfjaldsk23adsfabcabc"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				) and not rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 2)
     _a						=		"ABABX"
     _a						=		"ABABZABABYABABX"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 3)
     _a						=		"AAAB"
     _a						=		"ABAAAAAB"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 4)
     _a						=		"abcdabcy"
     _a						=		"abcxabcdabxabcdabcdabcy"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

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


if __name__ == "__main__":
   test_rabin_karp()

