




from __future__ import annotations

from collections import deque





class 	lowerCamelCase_							:


 '''simple docstring'''







 def __init__(							self  :		Optional[Any]    ,    _lowerCAmelCase  :		list[str]						):
       SCREAMING_SNAKE_CASE_     						=      []
       self.adlist.append(
           {'value': '', 'next_states': [], 'fail_state': 0, 'output': []}						)

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



 def 				lowerCAmelCase_  (							self  :		Optional[int]    ,    _lowerCAmelCase  :		int    ,    _lowerCAmelCase  :		str						):
       for state in self.adlist[current_state]["next_states"]:
             if char == self.adlist[state]["value"]:
                   return state
       return None



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



 def 				lowerCAmelCase_  (							self  :		str						):
       SCREAMING_SNAKE_CASE_     						=      deque()
       for node in self.adlist[0]["next_states"]:
             q.append(_lowerCAmelCase						)
             SCREAMING_SNAKE_CASE_     						=      0
       while q:
             SCREAMING_SNAKE_CASE_     						=      q.popleft()
             for child in self.adlist[r]["next_states"]:
                   q.append(_lowerCAmelCase						)
                   SCREAMING_SNAKE_CASE_     						=      self.adlist[r]['fail_state']
                   while (
                       self.find_next_state(_lowerCAmelCase    ,    self.adlist[child]['value']						) is None
                       and state != 0
                   ):
                         SCREAMING_SNAKE_CASE_     						=      self.adlist[state]['fail_state']
                   SCREAMING_SNAKE_CASE_     						=      self.find_next_state(
                       _lowerCAmelCase    ,    self.adlist[child]['value']						)
                   if self.adlist[child]["fail_state"] is None:
                         SCREAMING_SNAKE_CASE_     						=      0
                   SCREAMING_SNAKE_CASE_     						=      (
                       self.adlist[child]['output']
                       + self.adlist[self.adlist[child]['fail_state']]['output']
                   )




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


if __name__ == "__main__":
   import doctest

   doctest.testmod()





from packaging import version

from .import_utils import is_accelerate_available


if is_accelerate_available():
   import accelerate

def  UpperCAmelCase_							(				__UpperCAmelCase						:     Optional[int]							) ->			int:
      if not is_accelerate_available():
            return method
      SCREAMING_SNAKE_CASE_     						=      version.parse(accelerate.__version__							).base_version
      if version.parse(__UpperCAmelCase							) < version.parse('0.17.0'							):
            return method

      def wrapper(self						:     Optional[int]      ,      *__UpperCAmelCase						:     Optional[Any]      ,      **__UpperCAmelCase						:     Optional[Any]							):
            if hasattr(self      ,      '_hf_hook'							) and hasattr(self._hf_hook      ,      'pre_forward'							):
                  self._hf_hook.pre_forward(self							)
            return method(self      ,      *__UpperCAmelCase      ,      **__UpperCAmelCase							)

      return wrapper