

from __future__ import annotations

from collections import deque

class 				a  :


						def __init__(       self						,					A_	):







										'''simple docstring'''


										_UpperCAmelCase       :		list[dict] 		=    []
										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						,					A_						,					A_	):







										'''simple docstring'''


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


						def        _UpperCAmelCase				(       self						,					A_	):







										'''simple docstring'''


										_UpperCAmelCase       :		str 		=    0
										for character in keyword:
														_UpperCAmelCase       :		List[str] 		=    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	)
																		_UpperCAmelCase       :		List[Any] 		=    len(self.adlist	) - 1
														else:
																		_UpperCAmelCase       :		Optional[int] 		=    next_state
										self.adlist[current_state]["output"].append(A_	)


						def        _UpperCAmelCase				(       self	):







										'''simple docstring'''


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





						def        _UpperCAmelCase				(       self						,					A_	):







										'''simple docstring'''


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


if __name__ == "__main__":
					import doctest

					doctest.testmod()





from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


SCREAMING_SNAKE_CASE_        =      {
    'configuration_nllb_moe': [
        'NLLB_MOE_PRETRAINED_CONFIG_ARCHIVE_MAP',
        'NllbMoeConfig',
    ]
}

try:
					if not is_torch_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					SCREAMING_SNAKE_CASE_        =      [
					    'NLLB_MOE_PRETRAINED_MODEL_ARCHIVE_LIST',
					    'NllbMoeForConditionalGeneration',
					    'NllbMoeModel',
					    'NllbMoePreTrainedModel',
					    'NllbMoeTop2Router',
					    'NllbMoeSparseMLP',
					]


if TYPE_CHECKING:
					from .configuration_nllb_moe import (
					    NLLB_MOE_PRETRAINED_CONFIG_ARCHIVE_MAP,
					    NllbMoeConfig,
					)

					try:
										if not is_torch_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_nllb_moe import (
										    NLLB_MOE_PRETRAINED_MODEL_ARCHIVE_LIST,
										    NllbMoeForConditionalGeneration,
										    NllbMoeModel,
										    NllbMoePreTrainedModel,
										    NllbMoeSparseMLP,
										    NllbMoeTopaRouter,
										)


else:
					import sys

					SCREAMING_SNAKE_CASE_        =      _LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)


