





from __future__ import annotations

from collections import deque

class SCREAMING_SNAKE_CASE_ :





					"""simple docstring"""


					def __init__( self	,  _lowerCAmelCase	):
										lowerCamelCase__       =       []
										self.adlist.append(
										    {"value": "", "next_states": [], "fail_state": 0, "output": []}	)

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





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





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





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






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


if __name__ == "__main__":
						import doctest

						doctest.testmod()








from typing import TYPE_CHECKING

from ...utils import _LazyModule


A_												=     {"tokenization_byt5": ["ByT5Tokenizer"]}


if TYPE_CHECKING:
						from .tokenization_byta import ByTaTokenizer
else:
						import sys

						A_												=     _LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)

