


"""simple docstring"""



from __future__ import annotations

from collections import deque







class _lowerCAmelCase							:







   def __init__(      self		,      UpperCamelCase__		)      ->						int:

       '''simple docstring'''




       snake_case       : Dict    =       []
       self.adlist.append(
           {"value": "", "next_states": [], "fail_state": 0, "output": []}		)

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







   def 					lowerCamelCase						(      self		,      UpperCamelCase__		,      UpperCamelCase__		)      ->						Tuple:

       '''simple docstring'''




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







   def 					lowerCamelCase						(      self		,      UpperCamelCase__		)      ->						Optional[Any]:

       '''simple docstring'''




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







   def 					lowerCamelCase						(      self		)      ->						str:

       '''simple docstring'''




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







   def 					lowerCamelCase						(      self		,      UpperCamelCase__		)      ->						Optional[int]:

       '''simple docstring'''




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


if __name__ == "__main__":
  import doctest

  doctest.testmod()






"""simple docstring"""




from operator import delitem, getitem, setitem

import pytest

from data_structures.hashing.hash_map import HashMap







def 				_UpperCAmelCase		(							lowerCamelCase__  ):





		"""simple docstring"""




		return getitem, k







def 				_UpperCAmelCase		(							lowerCamelCase__      ,	lowerCamelCase__  ):





		"""simple docstring"""




		return setitem, k, v







def 				_UpperCAmelCase		(							lowerCamelCase__  ):





		"""simple docstring"""




		return delitem, k







def 				_UpperCAmelCase		(							lowerCamelCase__      ,	lowerCamelCase__      ,	*lowerCamelCase__  ):





		"""simple docstring"""




		try:
				return fun(lowerCamelCase__      ,	*lowerCamelCase__  ), None
		except Exception as e:
				return None, e


__lowerCAmelCase     :				Optional[Any]    				=    (
    _set("key_a", "val_a"),
    _set("key_b", "val_b"),
)

__lowerCAmelCase     :				Optional[int]    				=    [
    _set("key_a", "val_a"),
    _set("key_a", "val_b"),
]

__lowerCAmelCase     :				List[Any]    				=    [
    _set("key_a", "val_a"),
    _set("key_b", "val_b"),
    _del("key_a"),
    _del("key_b"),
    _set("key_a", "val_a"),
    _del("key_a"),
]

__lowerCAmelCase     :				int    				=    [
    _get("key_a"),
    _del("key_a"),
    _set("key_a", "val_a"),
    _del("key_a"),
    _del("key_a"),
    _get("key_a"),
]

__lowerCAmelCase     :				Optional[Any]    				=    [
    *[_set(x, x) for x in range(5)],  # guaranteed upsize
]

__lowerCAmelCase     :				Any    				=    [
    *[_set(x, x) for x in range(5)],  # guaranteed upsize
    *[_del(x) for x in range(5)],
    _set("key_a", "val_b"),
]







@pytest.mark.parametrize(
    """operations"""      ,	(
        pytest.param(_add_items      ,	id="""add items"""  ),
        pytest.param(_overwrite_items      ,	id="""overwrite items"""  ),
        pytest.param(_delete_items      ,	id="""delete items"""  ),
        pytest.param(_access_absent_items      ,	id="""access absent items"""  ),
        pytest.param(_add_with_resize_up      ,	id="""add with resize up"""  ),
        pytest.param(_add_with_resize_down      ,	id="""add with resize down"""  ),
    )      ,	)
def 				_UpperCAmelCase		(							lowerCamelCase__  ):





		"""simple docstring"""




		lowerCAmelCase__   = HashMap(initial_block_size=4  )
		lowerCAmelCase__   = {}
		for _, (fun, *args) in enumerate(lowerCamelCase__  ):
				lowerCAmelCase__ ,       lowerCAmelCase__   = _run_operation(lowerCamelCase__      ,	lowerCamelCase__      ,	*lowerCamelCase__  )
				lowerCAmelCase__ ,       lowerCAmelCase__   = _run_operation(lowerCamelCase__      ,	lowerCamelCase__      ,	*lowerCamelCase__  )
				assert my_res == py_res
				assert str(lowerCamelCase__  ) == str(lowerCamelCase__  )
				assert set(lowerCamelCase__  ) == set(lowerCamelCase__  )
				assert len(lowerCamelCase__  ) == len(lowerCamelCase__  )
				assert set(my.items()  ) == set(py.items()  )







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




		def is_public(lowerCamelCase__  ) -> bool:
				return not name.startswith("""_"""  )

		lowerCAmelCase__   = {name for name in dir({}  ) if is_public(lowerCamelCase__  )}
		lowerCAmelCase__   = {name for name in dir(HashMap()  ) if is_public(lowerCamelCase__  )}

		assert dict_public_names > hash_public_names




