



"""simple docstring"""

from __future__ import annotations

from collections import deque
class     lowerCAmelCase__						:


	'''simple docstring'''







	def __init__(      self				:       List[Any]     ,       _SCREAMING_SNAKE_CASE				:       list[str]    )						->	Any:





					"""simple docstring"""


					SCREAMING_SNAKE_CASE						:							list[dict]							=     []
					self.adlist.append(
					    {'value': '', 'next_states': [], 'fail_state': 0, 'output': []}    )

					for keyword in keywords:
									self.add_keyword(_SCREAMING_SNAKE_CASE    )
					self.set_fail_transitions()





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





					"""simple docstring"""


					for state in self.adlist[current_state]["next_states"]:
									if char == self.adlist[state]["value"]:
													return state
					return None





	def 			_lowerCAmelCase     (      self				:       str     ,       _SCREAMING_SNAKE_CASE				:       str    )						->	None:





					"""simple docstring"""


					SCREAMING_SNAKE_CASE						:							List[Any]							=     0
					for character in keyword:
									SCREAMING_SNAKE_CASE						:							str							=     self.find_next_state(_SCREAMING_SNAKE_CASE     ,       _SCREAMING_SNAKE_CASE    )
									if next_state is None:
													self.adlist.append(
													    {
													        'value': character,
													        'next_states': [],
													        'fail_state': 0,
													        'output': [],
													    }    )
													self.adlist[current_state]["next_states"].append(len(self.adlist    ) - 1    )
													SCREAMING_SNAKE_CASE						:							List[str]							=     len(self.adlist    ) - 1
									else:
													SCREAMING_SNAKE_CASE						:							Tuple							=     next_state
					self.adlist[current_state]["output"].append(_SCREAMING_SNAKE_CASE    )





	def 			_lowerCAmelCase     (      self				:       Tuple    )						->	None:





					"""simple docstring"""


					SCREAMING_SNAKE_CASE						:							deque							=     deque()
					for node in self.adlist[0]["next_states"]:
									q.append(_SCREAMING_SNAKE_CASE    )
									SCREAMING_SNAKE_CASE						:							Any							=     0
					while q:
									SCREAMING_SNAKE_CASE						:							Tuple							=     q.popleft()
									for child in self.adlist[r]["next_states"]:
													q.append(_SCREAMING_SNAKE_CASE    )
													SCREAMING_SNAKE_CASE						:							Union[str, Any]							=     self.adlist[r]['fail_state']
													while (
													    self.find_next_state(_SCREAMING_SNAKE_CASE     ,       self.adlist[child]['value']    ) is None
													    and state != 0
													):
																	SCREAMING_SNAKE_CASE						:							str							=     self.adlist[state]['fail_state']
													SCREAMING_SNAKE_CASE						:							List[Any]							=     self.find_next_state(
													    _SCREAMING_SNAKE_CASE     ,       self.adlist[child]['value']    )
													if self.adlist[child]["fail_state"] is None:
																	SCREAMING_SNAKE_CASE						:							Tuple							=     0
													SCREAMING_SNAKE_CASE						:							Union[str, Any]							=     (
													    self.adlist[child]['output']
													    + self.adlist[self.adlist[child]['fail_state']]['output']
													)







	def 			_lowerCAmelCase     (      self				:       Tuple     ,       _SCREAMING_SNAKE_CASE				:       str    )						->	dict[str, list[int]]:





					"""simple docstring"""


					SCREAMING_SNAKE_CASE						:							dict							=     {}  # returns a dict with keywords and list of its occurrences
					SCREAMING_SNAKE_CASE						:							int							=     0
					for i in range(len(_SCREAMING_SNAKE_CASE    )    ):
									while (
									    self.find_next_state(_SCREAMING_SNAKE_CASE     ,       string[i]    ) is None
									    and current_state != 0
									):
													SCREAMING_SNAKE_CASE						:							Dict							=     self.adlist[current_state]['fail_state']
									SCREAMING_SNAKE_CASE						:							str							=     self.find_next_state(_SCREAMING_SNAKE_CASE     ,       string[i]    )
									if next_state is None:
													SCREAMING_SNAKE_CASE						:							Optional[Any]							=     0
									else:
													SCREAMING_SNAKE_CASE						:							Any							=     next_state
													for key in self.adlist[current_state]["output"]:
																	if key not in result:
																					SCREAMING_SNAKE_CASE						:							Dict							=     []
																	result[key].append(i - len(_SCREAMING_SNAKE_CASE    ) + 1    )
					return result


if __name__ == "__main__":
							import doctest

							doctest.testmod()










"""simple docstring"""

def  __snake_case							(	__A      :						int							,		__A      :						int     )     ->       float:






				'''simple docstring'''
				return base * power(__A							,		(exponent - 1)     ) if exponent else 1


if __name__ == "__main__":
							print('Raise base to the power of exponent using recursion...')
							A_						:    str				=      int(input('Enter the base: ').strip())
							A_						:    Dict				=      int(input('Enter the exponent: ').strip())
							A_						:    List[str]				=      power(base, abs(exponent))
							if exponent < 0:  # power() does not properly deal w/ negative exponents
														A_						:    Any				=      1 / result
							print(f'''{base} to the power of {exponent} is {result}''')





