





"""simple docstring"""




from __future__ import annotations





def   lowerCamelCase__       (       UpperCamelCase__     :    str    ,      UpperCamelCase__     :    str  )     ->	bool:



					'''simple docstring'''




					_snake_case													=			get_failure_array(UpperCamelCase__  )

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

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





def   lowerCamelCase__       (       UpperCamelCase__     :    str  )     ->	list[int]:



					'''simple docstring'''




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


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

					# Test 2)
					UpperCAmelCase_ 							=       """ABABX"""
					UpperCAmelCase_ 							=       """ABABZABABYABABX"""
					assert kmp(pattern, text)

					# Test 3)
					UpperCAmelCase_ 							=       """AAAB"""
					UpperCAmelCase_ 							=       """ABAAAAAB"""
					assert kmp(pattern, text)

					# Test 4)
					UpperCAmelCase_ 							=       """abcdabcy"""
					UpperCAmelCase_ 							=       """abcxabcdabxabcdabcdabcy"""
					assert kmp(pattern, text)

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










def   lowerCamelCase__       (       UpperCamelCase__     :    list[list[int]]    ,      UpperCamelCase__     :    int    ,      UpperCamelCase__     :    int    ,      UpperCamelCase__     :    list[int]  )     ->	bool:



					'''simple docstring'''




					if graph[path[curr_ind - 1]][next_ver] == 0:
										return False

					# 2. Validate that next vertex is not already in path
					return not any(vertex == next_ver for vertex in path  )





def   lowerCamelCase__       (       UpperCamelCase__     :    list[list[int]]    ,      UpperCamelCase__     :    list[int]    ,      UpperCamelCase__     :    int  )     ->	bool:



					'''simple docstring'''




					if curr_ind == len(UpperCamelCase__  ):
										# return whether path exists between current and starting vertices
										return graph[path[curr_ind - 1]][path[0]] == 1

					# Recursive Step
					for next_ver in range(0    ,      len(UpperCamelCase__  )  ):
										if valid_connection(UpperCamelCase__    ,      UpperCamelCase__    ,      UpperCamelCase__    ,      UpperCamelCase__  ):
															# Insert current vertex  into path as next transition
															_snake_case													=			next_ver
															# Validate created path
															if util_hamilton_cycle(UpperCamelCase__    ,      UpperCamelCase__    ,      curr_ind + 1  ):
																				return True
															# Backtrack
															_snake_case													=			-1
					return False





def   lowerCamelCase__       (       UpperCamelCase__     :    list[list[int]]    ,      UpperCamelCase__     :    int = 0  )     ->	list[int]:



					'''simple docstring'''




					_snake_case													=			[-1] * (len(UpperCamelCase__  ) + 1)
					# initialize start and end of path with starting index
					_snake_case													=			_snake_case													=			start_index
					# evaluate and if we find answer return path either return empty array
					return path if util_hamilton_cycle(UpperCamelCase__    ,      UpperCamelCase__    ,      1  ) else []



