

"""simple docstring"""






from __future__ import annotations

from collections import deque







class       snake_case__  :







			def __init__(			self			: Dict			,  lowercase			: list[str]  ):





								'''simple docstring'''



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

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







			def 			__lowerCAmelCase				(			self			: Union[str, Any]			,  lowercase			: int			,  lowercase			: str  ):





								'''simple docstring'''



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







			def 			__lowerCAmelCase				(			self			: Optional[int]			,  lowercase			: str  ):





								'''simple docstring'''



								UpperCAmelCase			:   Dict      =				0
								for character in keyword:
													UpperCAmelCase			:   Dict      =				self.find_next_state(lowercase			,  lowercase  )
													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  )
																		UpperCAmelCase			:   List[str]      =				len(self.adlist  ) - 1
													else:
																		UpperCAmelCase			:   List[Any]      =				next_state
								self.adlist[current_state]["output"].append(lowercase  )







			def 			__lowerCAmelCase				(			self			: Any  ):





								'''simple docstring'''



								UpperCAmelCase			:   deque      =				deque()
								for node in self.adlist[0]["next_states"]:
													q.append(lowercase  )
													UpperCAmelCase			:   int      =				0
								while q:
													UpperCAmelCase			:   Dict      =				q.popleft()
													for child in self.adlist[r]["next_states"]:
																		q.append(lowercase  )
																		UpperCAmelCase			:   Any      =				self.adlist[r]["fail_state"]
																		while (
																		    self.find_next_state(lowercase			,  self.adlist[child]["value"]  ) is None
																		    and state != 0
																		):
																							UpperCAmelCase			:   Optional[int]      =				self.adlist[state]["fail_state"]
																		UpperCAmelCase			:   Optional[Any]      =				self.find_next_state(
																		    lowercase			,  self.adlist[child]["value"]  )
																		if self.adlist[child]["fail_state"] is None:
																							UpperCAmelCase			:   List[str]      =				0
																		UpperCAmelCase			:   List[str]      =				(
																		    self.adlist[child]["output"]
																		    + self.adlist[self.adlist[child]["fail_state"]]["output"]
																		)







			def 			__lowerCAmelCase				(			self			: List[str]			,  lowercase			: str  ):





								'''simple docstring'''



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


if __name__ == "__main__":
	import doctest

	doctest.testmod()





"""simple docstring"""






def   lowercase_	(    _lowercase       :		list							,      _lowercase       :		int							,      _lowercase       :		int = 0							,      _lowercase       :		int = 0	):




					'''simple docstring'''






					UpperCAmelCase			:   Tuple      =				right or len(_lowercase	) - 1
					if left > right:
										return -1
					elif list_data[left] == key:
										return left
					elif list_data[right] == key:
										return right
					else:
										return search(_lowercase							,      _lowercase							,      left + 1							,      right - 1	)


if __name__ == "__main__":
	import doctest

	doctest.testmod()


