



"""simple docstring"""






from __future__ import annotations

from collections import deque



class     A__     :




	'''simple docstring'''





	def __init__(  self:	Optional[int] ,    _SCREAMING_SNAKE_CASE:	list[str])       -> Dict:

				"""simple docstring"""

				__lowerCAmelCase   :						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 							_SCREAMING_SNAKE_CASE     (  self:	Any ,    _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 							_SCREAMING_SNAKE_CASE     (  self:	Optional[int] ,    _SCREAMING_SNAKE_CASE:	str)       -> None:

				"""simple docstring"""

				__lowerCAmelCase   :						List[Any]				= 0
				for character in keyword:
							__lowerCAmelCase   :						Union[str, Any]				= 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)
										__lowerCAmelCase   :						Optional[int]				= len(self.adlist) - 1
							else:
										__lowerCAmelCase   :						Optional[Any]				= next_state
				self.adlist[current_state]["output"].append(_SCREAMING_SNAKE_CASE)

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

				"""simple docstring"""

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







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

				"""simple docstring"""

				__lowerCAmelCase   :						dict				= {}  # returns a dict with keywords and list of its occurrences
				__lowerCAmelCase   :						Optional[Any]				= 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
							):
										__lowerCAmelCase   :						Any				= self.adlist[current_state]["fail_state"]
							__lowerCAmelCase   :						Union[str, Any]				= self.find_next_state(_SCREAMING_SNAKE_CASE ,    string[i])
							if next_state is None:
										__lowerCAmelCase   :						List[str]				= 0
							else:
										__lowerCAmelCase   :						List[str]				= next_state
										for key in self.adlist[current_state]["output"]:
													if key not in result:
																__lowerCAmelCase   :						Optional[Any]				= []
													result[key].append(i - len(_SCREAMING_SNAKE_CASE) + 1)
				return result


if __name__ == "__main__":
	import doctest

	doctest.testmod()




"""simple docstring"""






from abc import ABC, abstractmethod
from argparse import ArgumentParser



class     A__     (						__SCREAMING_SNAKE_CASE							):




	'''simple docstring'''





	@staticmethod
	@abstractmethod
	def 							_SCREAMING_SNAKE_CASE     (  _SCREAMING_SNAKE_CASE:	ArgumentParser)       -> str:

				"""simple docstring"""

				raise NotImplementedError()







	@abstractmethod
	def 							_SCREAMING_SNAKE_CASE     (  self:	List[str])       -> str:

				"""simple docstring"""

				raise NotImplementedError()