# Lint as: python3
import dataclasses
import re
from dataclasses import dataclass
from functools import total_ordering
from typing import Optional, Union


A_      =      re.compile(R"^(?P<major>\d+)" R"\.(?P<minor>\d+)" R"\.(?P<patch>\d+)$")






@total_ordering
@dataclass
class      __lowercase					:
						lowercase					 =     42
						lowercase					 =     None
						lowercase					 =     None
						lowercase					 =     None
						lowercase					 =     None

						def        __a		(	self				:      int   )							->		str:


									'''simple docstring'''

									lowercase		,lowercase		,lowercase							=		_str_to_version_tuple(self.version_str   )

						def __repr__(	self				:      Union[str, Any]   )							->		int:


									'''simple docstring'''

									return f'{self.tuple[0]}.{self.tuple[1]}.{self.tuple[2]}'

						@property
						def        __a		(	self				:      Dict   )							->		Union[str, Any]:


									'''simple docstring'''

									return self.major, self.minor, self.patch

						def        __a		(	self				:      Optional[Any]							,							__lowerCamelCase				:      Any   )							->		Dict:


									'''simple docstring'''

									if isinstance(__lowerCamelCase							,							__lowerCamelCase   ):
												return Version(__lowerCamelCase   )
									elif isinstance(__lowerCamelCase							,							__lowerCamelCase   ):
												return other
									raise TypeError(f'{other} (type {type(__lowerCamelCase   )}) cannot be compared to version.'   )

						def __eq__(	self				:      Tuple							,							__lowerCamelCase				:      Tuple   )							->		List[Any]:


									'''simple docstring'''

									try:
												lowercase							=		self._validate_operand(__lowerCamelCase   )
									except (TypeError, ValueError):
												return False
									else:
												return self.tuple == other.tuple

						def __lt__(	self				:      Any							,							__lowerCamelCase				:      Union[str, Any]   )							->		int:


									'''simple docstring'''

									lowercase							=		self._validate_operand(__lowerCamelCase   )
									return self.tuple < other.tuple

						def __hash__(	self				:      int   )							->		str:


									'''simple docstring'''

									return hash(_version_tuple_to_str(self.tuple   )   )

						@classmethod
						def        __a		(	cls				:      List[str]							,							__lowerCamelCase				:      Any   )							->		int:


									'''simple docstring'''

									lowercase							=		{f.name for f in dataclasses.fields(cls   )}
									return cls(**{k: v for k, v in dic.items() if k in field_names}   )



						def        __a		(	self				:      Union[str, Any]   )							->		str:


									'''simple docstring'''

									return self.version_str






def        __UpperCAmelCase    (       UpperCAmelCase       )->       List[str]:



			"""simple docstring"""







			lowercase							=		_VERSION_REG.match(UpperCAmelCase       )
			if not res:
						raise ValueError(f'Invalid version \'{version_str}\'. Format should be x.y.z with {{x,y,z}} being digits.'       )
			return tuple(int(UpperCAmelCase       ) for v in [res.group('''major'''       ), res.group('''minor'''       ), res.group('''patch'''       )]       )






def        __UpperCAmelCase    (       UpperCAmelCase       )->       int:



			"""simple docstring"""







			return ".".join(str(UpperCAmelCase       ) for v in version_tuple       )






from __future__ import annotations

from collections import deque






class      __lowercase					:

						def __init__(	self				:      Dict							,							__lowerCamelCase				:      list[str]   )							->		List[str]:


									'''simple docstring'''

									lowercase							=		[]
									self.adlist.append(
									    {'''value''': '''''', '''next_states''': [], '''fail_state''': 0, '''output''': []}   )

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

						def        __a		(	self				:      str							,							__lowerCamelCase				:      int							,							__lowerCamelCase				:      str   )							->		int | None:


									'''simple docstring'''

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

						def        __a		(	self				:      List[Any]							,							__lowerCamelCase				:      str   )							->		None:


									'''simple docstring'''

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

						def        __a		(	self				:      int   )							->		None:


									'''simple docstring'''

									lowercase							=		deque()
									for node in self.adlist[0]["next_states"]:
												q.append(__lowerCamelCase   )
												lowercase							=		0
									while q:
												lowercase							=		q.popleft()
												for child in self.adlist[r]["next_states"]:
															q.append(__lowerCamelCase   )
															lowercase							=		self.adlist[r]['''fail_state''']
															while (
															    self.find_next_state(__lowerCamelCase							,							self.adlist[child]['''value''']   ) is None
															    and state != 0
															):
																		lowercase							=		self.adlist[state]['''fail_state''']
															lowercase							=		self.find_next_state(
															    __lowerCamelCase							,							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        __a		(	self				:      List[str]							,							__lowerCamelCase				:      str   )							->		dict[str, list[int]]:


									'''simple docstring'''

									lowercase							=		{}  # returns a dict with keywords and list of its occurrences
									lowercase							=		0
									for i in range(len(__lowerCamelCase   )   ):
												while (
												    self.find_next_state(__lowerCamelCase							,							string[i]   ) is None
												    and current_state != 0
												):
															lowercase							=		self.adlist[current_state]['''fail_state''']
												lowercase							=		self.find_next_state(__lowerCamelCase							,							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(__lowerCamelCase   ) + 1   )
									return result


if __name__ == "__main__":
						import doctest

						doctest.testmod()





