


'''simple docstring'''





from __future__ import annotations

from collections import deque




class 				UpperCAmelCase			:


 def __init__(      self							:	List[str]			,       __lowerCamelCase							:	list[str] ):
    UpperCAmelCase__	:list[dict]      =      []
    self.adlist.append(
        {'''value''': '''''', '''next_states''': [], '''fail_state''': 0, '''output''': []} )

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


 def        __SCREAMING_SNAKE_CASE					(      self							:	List[Any]			,       __lowerCamelCase							:	int			,       __lowerCamelCase							:	str ):
    for state in self.adlist[current_state]["next_states"]:
       if char == self.adlist[state]["value"]:
          return state
    return None


 def        __SCREAMING_SNAKE_CASE					(      self							:	Any			,       __lowerCamelCase							:	str ):
    UpperCAmelCase__	:Tuple      =      0
    for character in keyword:
       UpperCAmelCase__	:int      =      self.find_next_state(__lowerCamelCase			,       __lowerCamelCase )
       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__	:int      =      next_state
    self.adlist[current_state]["output"].append(__lowerCamelCase )


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





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


if __name__ == "__main__":
    import doctest

    doctest.testmod()







'''simple docstring'''





from ..utils import DummyObject, requires_backends




class 				UpperCAmelCase			(			metaclass=_snake_case						):
 UpperCAmelCase				=					["note_seq"]


 def __init__(      self							:	List[str]			,       *__lowerCamelCase							:	int			,       **__lowerCamelCase							:	Optional[int] ):
    requires_backends(self			,       ['''note_seq'''] )


 @classmethod
 def        __SCREAMING_SNAKE_CASE					(      cls							:	Optional[Any]			,       *__lowerCamelCase							:	Dict			,       **__lowerCamelCase							:	Optional[Any] ):
    requires_backends(cls			,       ['''note_seq'''] )





 @classmethod
 def        __SCREAMING_SNAKE_CASE					(      cls							:	str			,       *__lowerCamelCase							:	Any			,       **__lowerCamelCase							:	Optional[Any] ):
    requires_backends(cls			,       ['''note_seq'''] )



