





from __future__ import annotations

from collections import deque





class 					A_					:







       """simple docstring"""





       def __init__(     self						:						str    ,__A						:						list[str]	)    ->       List[str]:
         _lowercase						    =			[]
         self.adlist.append(
             {'value': '', 'next_states': [], 'fail_state': 0, 'output': []}	)

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







       def  __UpperCAmelCase			(     self						:						List[str]    ,__A						:						int    ,__A						:						str	)    ->       int | None:
         for state in self.adlist[current_state]["next_states"]:
           if char == self.adlist[state]["value"]:
             return state
         return None







       def  __UpperCAmelCase			(     self						:						Optional[int]    ,__A						:						str	)    ->       None:
         _lowercase						    =			0
         for character in keyword:
           _lowercase						    =			self.find_next_state(__A    ,__A	)
           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	)
             _lowercase						    =			len(self.adlist	) - 1
           else:
             _lowercase						    =			next_state
         self.adlist[current_state]["output"].append(__A	)







       def  __UpperCAmelCase			(     self						:						Union[str, Any]	)    ->       None:
         _lowercase						    =			deque()
         for node in self.adlist[0]["next_states"]:
           q.append(__A	)
           _lowercase						    =			0
         while q:
           _lowercase						    =			q.popleft()
           for child in self.adlist[r]["next_states"]:
             q.append(__A	)
             _lowercase						    =			self.adlist[r]['fail_state']
             while (
                 self.find_next_state(__A    ,self.adlist[child]['value']	) is None
                 and state != 0
             ):
               _lowercase						    =			self.adlist[state]['fail_state']
             _lowercase						    =			self.find_next_state(
                 __A    ,self.adlist[child]['value']	)
             if self.adlist[child]["fail_state"] is None:
               _lowercase						    =			0
             _lowercase						    =			(
                 self.adlist[child]['output']
                 + self.adlist[self.adlist[child]['fail_state']]['output']
             )







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


if __name__ == "__main__":
      import doctest

      doctest.testmod()






'''simple docstring'''

from string import ascii_uppercase

__lowerCAmelCase				:      Union[str, Any]						      ={str(ord(c) - 55): c for c in ascii_uppercase}





def 		UpperCamelCase							(				_lowerCamelCase   :   int		,			_lowerCamelCase   :   int			):
    if isinstance(_lowerCamelCase		,			_lowerCamelCase			):
        raise TypeError("int() can't convert non-string with explicit base"			)
    if num < 0:
        raise ValueError("parameter must be positive int"			)
    if isinstance(_lowerCamelCase		,			_lowerCamelCase			):
        raise TypeError("'str' object cannot be interpreted as an integer"			)
    if isinstance(_lowerCamelCase		,			_lowerCamelCase			):
        raise TypeError("'float' object cannot be interpreted as an integer"			)
    if base in (0, 1):
        raise ValueError("base must be >= 2"			)
    if base > 36:
        raise ValueError("base must be <= 36"			)
    A__							=     ""
    A__							=     0
    A__							=     0
    while div != 1:
        A__,      A__							=     divmod(_lowerCamelCase		,			_lowerCamelCase			)
        if base >= 11 and 9 < mod < 36:
            A__							=     ALPHABET_VALUES[str(_lowerCamelCase			)]
        else:
            A__							=     str(_lowerCamelCase			)
        new_value += actual_value
        A__							=     num // base
        A__							=     div
        if div == 0:
            return str(new_value[::-1]			)
        elif div == 1:
            new_value += str(_lowerCamelCase			)
            return str(new_value[::-1]			)

    return new_value[::-1]


if __name__ == "__main__":
  import doctest

  doctest.testmod()

  for base in range(2, 37):
    for num in range(1000):
      assert int(decimal_to_any(num, base), base) == num, (
          num,
          base,
          decimal_to_any(num, base),
          int(decimal_to_any(num, base), base),
      )



