





'''simple docstring'''






from __future__ import annotations

from collections import deque







class 		UpperCAmelCase   :


  """simple docstring"""







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

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


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


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




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


if __name__ == "__main__":
      import doctest

      doctest.testmod()













'''simple docstring'''






from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_sentencepiece_available,
    is_speech_available,
    is_tf_available,
    is_torch_available,
)


__lowerCamelCase						: str		=   {
    'configuration_speech_to_text': ['SPEECH_TO_TEXT_PRETRAINED_CONFIG_ARCHIVE_MAP', 'Speech2TextConfig'],
    'processing_speech_to_text': ['Speech2TextProcessor'],
}

try:
      if not is_sentencepiece_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __lowerCamelCase						: List[str]		=   ['Speech2TextTokenizer']

try:
      if not is_speech_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __lowerCamelCase						: str		=   ['Speech2TextFeatureExtractor']

try:
      if not is_tf_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __lowerCamelCase						: Optional[Any]		=   [
          'TF_SPEECH_TO_TEXT_PRETRAINED_MODEL_ARCHIVE_LIST',
          'TFSpeech2TextForConditionalGeneration',
          'TFSpeech2TextModel',
          'TFSpeech2TextPreTrainedModel',
      ]

try:
      if not is_torch_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __lowerCamelCase						: Union[str, Any]		=   [
          'SPEECH_TO_TEXT_PRETRAINED_MODEL_ARCHIVE_LIST',
          'Speech2TextForConditionalGeneration',
          'Speech2TextModel',
          'Speech2TextPreTrainedModel',
      ]


if TYPE_CHECKING:
      from .configuration_speech_to_text import SPEECH_TO_TEXT_PRETRAINED_CONFIG_ARCHIVE_MAP, SpeechaTextConfig
      from .processing_speech_to_text import SpeechaTextProcessor

      try:
            if not is_sentencepiece_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .tokenization_speech_to_text import SpeechaTextTokenizer

      try:
            if not is_speech_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .feature_extraction_speech_to_text import SpeechaTextFeatureExtractor

      try:
            if not is_tf_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_tf_speech_to_text import (
                TF_SPEECH_TO_TEXT_PRETRAINED_MODEL_ARCHIVE_LIST,
                TFSpeechaTextForConditionalGeneration,
                TFSpeechaTextModel,
                TFSpeechaTextPreTrainedModel,
            )

      try:
            if not is_torch_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_speech_to_text import (
                SPEECH_TO_TEXT_PRETRAINED_MODEL_ARCHIVE_LIST,
                SpeechaTextForConditionalGeneration,
                SpeechaTextModel,
                SpeechaTextPreTrainedModel,
            )

else:
      import sys

      __lowerCamelCase						: Optional[int]		=   _LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)






