





"""simple docstring"""






import json
import os
import shutil
import tempfile
import unittest
from multiprocessing import get_context
from pathlib import Path

import datasets
import numpy as np
from datasets import load_dataset
from parameterized import parameterized

from transformers import AutoProcessor
from transformers.models.wavaveca import WavaVecaCTCTokenizer, WavaVecaFeatureExtractor
from transformers.models.wavaveca.tokenization_wavaveca import VOCAB_FILES_NAMES
from transformers.testing_utils import require_pyctcdecode, require_torch, require_torchaudio, slow
from transformers.utils import FEATURE_EXTRACTOR_NAME, is_pyctcdecode_available, is_torch_available

from ..wavaveca.test_feature_extraction_wavaveca import floats_list


if is_pyctcdecode_available():
		from huggingface_hub import snapshot_download
		from pyctcdecode import BeamSearchDecoderCTC

		from transformers.models.wavaveca_with_lm import WavaVecaProcessorWithLM
		from transformers.models.wavaveca_with_lm.processing_wavaveca_with_lm import WavaVecaDecoderWithLMOutput

if is_torch_available():
		from transformers import WavaVecaForCTC



@require_pyctcdecode
class 					__UpperCAmelCase							(						unittest.TestCase  ):
				def       UpperCAmelCase      (		self    :			Any    )	->	Dict:



							'''simple docstring'''



							a__  :	Dict		 =			"| <pad> <unk> <s> </s> a b c d e f g h i j k".split()
							a__  :	Any		 =			dict(zip(a_	, range(len(a_    )    )    )    )

							a__  :	int		 =			{
							    "unk_token": "<unk>",
							    "bos_token": "<s>",
							    "eos_token": "</s>",
							}
							a__  :	Optional[Any]		 =			{
							    "feature_size": 1,
							    "padding_value": 0.0,
							    "sampling_rate": 1_60_00,
							    "return_attention_mask": False,
							    "do_normalize": True,
							}

							a__  :	Optional[int]		 =			tempfile.mkdtemp()
							a__  :	Tuple		 =			os.path.join(self.tmpdirname	, VOCAB_FILES_NAMES["vocab_file"]    )
							a__  :	Tuple		 =			os.path.join(self.tmpdirname	, a_    )
							with open(self.vocab_file	, "w"	, encoding="utf-8"    ) as fp:
										fp.write(json.dumps(a_    ) + "\n"    )

							with open(self.feature_extraction_file	, "w"	, encoding="utf-8"    ) as fp:
										fp.write(json.dumps(a_    ) + "\n"    )

							# load decoder from hub
							a__  :	Tuple		 =			"hf-internal-testing/ngram-beam-search-decoder"
				def       UpperCAmelCase      (		self    :			List[Any]	, **a_    :			Dict    )	->	List[str]:



							'''simple docstring'''



							a__  :	Optional[int]		 =			self.add_kwargs_tokens_map.copy()
							kwargs.update(a_    )
							return WavaVecaCTCTokenizer.from_pretrained(self.tmpdirname	, **a_    )
				def       UpperCAmelCase      (		self    :			Dict	, **a_    :			str    )	->	Optional[int]:



							'''simple docstring'''



							return WavaVecaFeatureExtractor.from_pretrained(self.tmpdirname	, **a_    )
				def       UpperCAmelCase      (		self    :			Any	, **a_    :			List[str]    )	->	Union[str, Any]:



							'''simple docstring'''



							return BeamSearchDecoderCTC.load_from_hf_hub(self.decoder_name	, **a_    )
				def       UpperCAmelCase      (		self    :			Optional[Any]    )	->	Optional[int]:



							'''simple docstring'''



							shutil.rmtree(self.tmpdirname    )
				def       UpperCAmelCase      (		self    :			List[str]    )	->	List[Any]:



							'''simple docstring'''



							a__  :	str		 =			self.get_tokenizer()
							a__  :	str		 =			self.get_feature_extractor()
							a__  :	Optional[Any]		 =			self.get_decoder()

							a__  :	List[Any]		 =			WavaVecaProcessorWithLM(tokenizer=a_	, feature_extractor=a_	, decoder=a_    )

							processor.save_pretrained(self.tmpdirname    )
							a__  :	Union[str, Any]		 =			WavaVecaProcessorWithLM.from_pretrained(self.tmpdirname    )

							# tokenizer
							self.assertEqual(processor.tokenizer.get_vocab()	, tokenizer.get_vocab()    )
							self.assertIsInstance(processor.tokenizer	, a_    )

							# feature extractor
							self.assertEqual(processor.feature_extractor.to_json_string()	, feature_extractor.to_json_string()    )
							self.assertIsInstance(processor.feature_extractor	, a_    )

							# decoder
							self.assertEqual(processor.decoder._alphabet.labels	, decoder._alphabet.labels    )
							self.assertEqual(
							    processor.decoder.model_container[decoder._model_key]._unigram_set	, decoder.model_container[decoder._model_key]._unigram_set	, )
							self.assertIsInstance(processor.decoder	, a_    )
				def       UpperCAmelCase      (		self    :			Tuple    )	->	List[str]:



							'''simple docstring'''



							a__  :	Tuple		 =			WavaVecaProcessorWithLM(
							    tokenizer=self.get_tokenizer()	, feature_extractor=self.get_feature_extractor()	, decoder=self.get_decoder()    )
							processor.save_pretrained(self.tmpdirname    )

							# make sure that error is thrown when decoder alphabet doesn't match
							a__  :	Dict		 =			WavaVecaProcessorWithLM.from_pretrained(
							    self.tmpdirname	, alpha=5.0	, beta=3.0	, score_boundary=-7.0	, unk_score_offset=3    )

							# decoder
							self.assertEqual(processor.language_model.alpha	, 5.0    )
							self.assertEqual(processor.language_model.beta	, 3.0    )
							self.assertEqual(processor.language_model.score_boundary	, -7.0    )
							self.assertEqual(processor.language_model.unk_score_offset	, 3    )
				def       UpperCAmelCase      (		self    :			List[str]    )	->	Any:



							'''simple docstring'''



							a__  :	Any		 =			self.get_tokenizer()
							# add token to trigger raise
							tokenizer.add_tokens(["xx"]    )
							with self.assertRaisesRegex(a_	, "include"    ):
										WavaVecaProcessorWithLM(
										    tokenizer=a_	, feature_extractor=self.get_feature_extractor()	, decoder=self.get_decoder()    )
				def       UpperCAmelCase      (		self    :			Optional[Any]    )	->	Dict:



							'''simple docstring'''



							a__  :	int		 =			self.get_feature_extractor()
							a__  :	List[Any]		 =			self.get_tokenizer()
							a__  :	Union[str, Any]		 =			self.get_decoder()

							a__  :	str		 =			WavaVecaProcessorWithLM(tokenizer=a_	, feature_extractor=a_	, decoder=a_    )

							a__  :	Dict		 =			floats_list((3, 10_00)    )

							a__  :	List[Any]		 =			feature_extractor(a_	, return_tensors="np"    )
							a__  :	Optional[Any]		 =			processor(a_	, return_tensors="np"    )

							for key in input_feat_extract.keys():
										self.assertAlmostEqual(input_feat_extract[key].sum()	, input_processor[key].sum()	, delta=1E-2    )
				def       UpperCAmelCase      (		self    :			str    )	->	Optional[int]:



							'''simple docstring'''



							a__  :	Optional[Any]		 =			self.get_feature_extractor()
							a__  :	Optional[Any]		 =			self.get_tokenizer()
							a__  :	Any		 =			self.get_decoder()

							a__  :	str		 =			WavaVecaProcessorWithLM(tokenizer=a_	, feature_extractor=a_	, decoder=a_    )

							a__  :	Optional[int]		 =			"This is a test string"

							a__  :	Union[str, Any]		 =			processor(text=a_    )

							a__  :	List[Any]		 =			tokenizer(a_    )

							for key in encoded_tok.keys():
										self.assertListEqual(encoded_tok[key]	, encoded_processor[key]    )
				def       UpperCAmelCase      (		self    :			Dict	, a_    :			Tuple=(2, 10, 16)	, a_    :			Optional[int]=77    )	->	Any:



							'''simple docstring'''



							np.random.seed(a_    )
							return np.random.rand(*a_    )
				def       UpperCAmelCase      (		self    :			Optional[Any]    )	->	Dict:



							'''simple docstring'''



							a__  :	int		 =			self.get_feature_extractor()
							a__  :	Dict		 =			self.get_tokenizer()
							a__  :	List[str]		 =			self.get_decoder()

							a__  :	List[Any]		 =			WavaVecaProcessorWithLM(tokenizer=a_	, feature_extractor=a_	, decoder=a_    )

							a__  :	List[Any]		 =			self._get_dummy_logits(shape=(10, 16)	, seed=13    )

							a__  :	Optional[int]		 =			processor.decode(a_    )

							a__  :	Optional[int]		 =			decoder.decode_beams(a_    )[0]

							self.assertEqual(decoded_decoder[0]	, decoded_processor.text    )
							self.assertEqual("</s> <s> </s>"	, decoded_processor.text    )
							self.assertEqual(decoded_decoder[-2]	, decoded_processor.logit_score    )
							self.assertEqual(decoded_decoder[-1]	, decoded_processor.lm_score    )
				@parameterized.expand([[None], ["fork"], ["spawn"]]    )
				def       UpperCAmelCase      (		self    :			Dict	, a_    :			Dict    )	->	Optional[Any]:



							'''simple docstring'''



							a__  :	Any		 =			self.get_feature_extractor()
							a__  :	List[str]		 =			self.get_tokenizer()
							a__  :	Dict		 =			self.get_decoder()

							a__  :	Optional[int]		 =			WavaVecaProcessorWithLM(tokenizer=a_	, feature_extractor=a_	, decoder=a_    )

							a__  :	List[Any]		 =			self._get_dummy_logits()

							# note: pool should be instantiated *after* Wav2Vec2ProcessorWithLM.
							#       otherwise, the LM won't be available to the pool's sub-processes.
							# manual logic used to allow parameterized test for both pool=None and pool=Pool(...)
							if pool_context is None:
										a__  :	Optional[Any]		 =			processor.batch_decode(a_    )
							else:
										with get_context(a_    ).Pool() as pool:
													a__  :	int		 =			processor.batch_decode(a_	, a_    )

							a__  :	Optional[Any]		 =			list(a_    )

							with get_context("fork"    ).Pool() as p:
										a__  :	List[Any]		 =			decoder.decode_beams_batch(a_	, a_    )

							a__ ,	a__ ,	a__  :	str		 =			[], [], []
							for beams in decoded_beams:
										texts_decoder.append(beams[0][0]    )
										logit_scores_decoder.append(beams[0][-2]    )
										lm_scores_decoder.append(beams[0][-1]    )

							self.assertListEqual(a_	, decoded_processor.text    )
							self.assertListEqual(["<s> <s> </s>", "<s> <s> <s>"]	, decoded_processor.text    )
							self.assertListEqual(a_	, decoded_processor.logit_score    )
							self.assertListEqual(a_	, decoded_processor.lm_score    )
				def       UpperCAmelCase      (		self    :			Tuple    )	->	Union[str, Any]:



							'''simple docstring'''



							a__  :	Optional[int]		 =			self.get_feature_extractor()
							a__  :	Union[str, Any]		 =			self.get_tokenizer()
							a__  :	int		 =			self.get_decoder()

							a__  :	List[str]		 =			WavaVecaProcessorWithLM(tokenizer=a_	, feature_extractor=a_	, decoder=a_    )

							a__  :	Optional[int]		 =			self._get_dummy_logits()

							a__  :	Dict		 =			15
							a__  :	Optional[int]		 =			-20.0
							a__  :	Optional[int]		 =			-4.0

							a__  :	Union[str, Any]		 =			processor.batch_decode(
							    a_	, beam_width=a_	, beam_prune_logp=a_	, token_min_logp=a_	, )
							a__  :	Any		 =			decoded_processor_out.text

							a__  :	Optional[Any]		 =			list(a_    )

							with get_context("fork"    ).Pool() as pool:
										a__  :	Union[str, Any]		 =			decoder.decode_beams_batch(
										    a_	, a_	, beam_width=a_	, beam_prune_logp=a_	, token_min_logp=a_	, )

							a__  :	Optional[int]		 =			[d[0][0] for d in decoded_decoder_out]
							a__  :	Tuple		 =			[d[0][2] for d in decoded_decoder_out]
							a__  :	Union[str, Any]		 =			[d[0][3] for d in decoded_decoder_out]

							self.assertListEqual(a_	, a_    )
							self.assertListEqual(["</s> <s> <s>", "<s> <s> <s>"]	, a_    )

							self.assertTrue(np.array_equal(a_	, decoded_processor_out.logit_score    )    )
							self.assertTrue(np.allclose([-20.054, -18.447]	, a_	, atol=1E-3    )    )

							self.assertTrue(np.array_equal(a_	, decoded_processor_out.lm_score    )    )
							self.assertTrue(np.allclose([-15.554, -13.9474]	, a_	, atol=1E-3    )    )
				def       UpperCAmelCase      (		self    :			List[Any]    )	->	Dict:



							'''simple docstring'''



							a__  :	Tuple		 =			self.get_feature_extractor()
							a__  :	List[Any]		 =			self.get_tokenizer()
							a__  :	Any		 =			self.get_decoder()

							a__  :	int		 =			WavaVecaProcessorWithLM(tokenizer=a_	, feature_extractor=a_	, decoder=a_    )

							a__  :	Tuple		 =			self._get_dummy_logits()

							a__  :	str		 =			2.0
							a__  :	Optional[int]		 =			5.0
							a__  :	Optional[int]		 =			-20.0
							a__  :	Any		 =			True

							a__  :	List[str]		 =			processor.batch_decode(
							    a_	, alpha=a_	, beta=a_	, unk_score_offset=a_	, lm_score_boundary=a_	, )
							a__  :	List[Any]		 =			decoded_processor_out.text

							a__  :	Tuple		 =			list(a_    )
							decoder.reset_params(
							    alpha=a_	, beta=a_	, unk_score_offset=a_	, lm_score_boundary=a_	, )

							with get_context("fork"    ).Pool() as pool:
										a__  :	Optional[int]		 =			decoder.decode_beams_batch(
										    a_	, a_	, )

							a__  :	int		 =			[d[0][0] for d in decoded_decoder_out]

							self.assertListEqual(a_	, a_    )
							self.assertListEqual(["<s> </s> <s> </s> </s>", "</s> </s> <s> </s> </s>"]	, a_    )
							a__  :	int		 =			processor.decoder.model_container[processor.decoder._model_key]
							self.assertEqual(lm_model.alpha	, 2.0    )
							self.assertEqual(lm_model.beta	, 5.0    )
							self.assertEqual(lm_model.unk_score_offset	, -20.0    )
							self.assertEqual(lm_model.score_boundary	, a_    )
				def       UpperCAmelCase      (		self    :			Dict    )	->	str:



							'''simple docstring'''



							a__  :	List[Any]		 =			WavaVecaProcessorWithLM.from_pretrained("hf-internal-testing/processor_with_lm"    )

							a__  :	Optional[Any]		 =			processor.decoder.model_container[processor.decoder._model_key]
							a__  :	Dict		 =			Path(language_model._kenlm_model.path.decode("utf-8"    )    ).parent.parent.absolute()

							a__  :	List[Any]		 =			os.listdir(a_    )
							a__  :	Optional[int]		 =			["alphabet.json", "language_model"]

							downloaded_decoder_files.sort()
							expected_decoder_files.sort()

							# test that only decoder relevant files from
							# https://huggingface.co/hf-internal-testing/processor_with_lm/tree/main
							# are downloaded and none of the rest (e.g. README.md, ...)
							self.assertListEqual(a_	, a_    )
				def       UpperCAmelCase      (		self    :			int    )	->	List[str]:



							'''simple docstring'''



							a__  :	Optional[int]		 =			snapshot_download("hf-internal-testing/processor_with_lm"    )

							a__  :	str		 =			WavaVecaProcessorWithLM.from_pretrained(a_    )

							a__  :	Union[str, Any]		 =			processor.decoder.model_container[processor.decoder._model_key]
							a__  :	List[str]		 =			Path(language_model._kenlm_model.path.decode("utf-8"    )    ).parent.parent.absolute()

							a__  :	List[Any]		 =			os.listdir(a_    )
							a__  :	Any		 =			os.listdir(a_    )

							local_decoder_files.sort()
							expected_decoder_files.sort()

							# test that both decoder form hub and local files in cache are the same
							self.assertListEqual(a_	, a_    )
				def       UpperCAmelCase      (		self    :			Optional[Any]    )	->	Any:



							'''simple docstring'''



							a__  :	List[Any]		 =			WavaVecaProcessorWithLM.from_pretrained("hf-internal-testing/processor_with_lm"    )
							a__  :	Optional[int]		 =			AutoProcessor.from_pretrained("hf-internal-testing/processor_with_lm"    )

							a__  :	List[str]		 =			floats_list((3, 10_00)    )

							a__  :	Tuple		 =			processor_wavaveca(a_	, return_tensors="np"    )
							a__  :	Any		 =			processor_auto(a_	, return_tensors="np"    )

							for key in input_wavaveca.keys():
										self.assertAlmostEqual(input_wavaveca[key].sum()	, input_auto[key].sum()	, delta=1E-2    )

							a__  :	Optional[int]		 =			self._get_dummy_logits()

							a__  :	Optional[Any]		 =			processor_wavaveca.batch_decode(a_    )
							a__  :	int		 =			processor_auto.batch_decode(a_    )

							self.assertListEqual(decoded_wavaveca.text	, decoded_auto.text    )
				def       UpperCAmelCase      (		self    :			Tuple    )	->	Optional[Any]:



							'''simple docstring'''



							a__  :	List[str]		 =			self.get_feature_extractor()
							a__  :	Optional[Any]		 =			self.get_tokenizer()
							a__  :	List[Any]		 =			self.get_decoder()

							a__  :	Any		 =			WavaVecaProcessorWithLM(tokenizer=a_	, feature_extractor=a_	, decoder=a_    )

							self.assertListEqual(
							    processor.model_input_names	, feature_extractor.model_input_names	, msg="`processor` and `feature_extractor` model input names do not match"	, )
				@staticmethod
				def       UpperCAmelCase      (		a_    :			Dict	, a_    :			Any    )	->	Dict:



							'''simple docstring'''



							a__  :	Tuple		 =			[d[key] for d in offsets]
							return retrieved_list
				def       UpperCAmelCase      (		self    :			Optional[Any]    )	->	Any:



							'''simple docstring'''



							a__  :	str		 =			WavaVecaProcessorWithLM.from_pretrained("hf-internal-testing/processor_with_lm"    )
							a__  :	Dict		 =			self._get_dummy_logits()[0]

							a__  :	Union[str, Any]		 =			processor.decode(a_	, output_word_offsets=a_    )
							# check Wav2Vec2CTCTokenizerOutput keys for word
							self.assertEqual(len(outputs.keys()    )	, 4    )
							self.assertTrue("text" in outputs    )
							self.assertTrue("word_offsets" in outputs    )
							self.assertTrue(isinstance(a_	, a_    )    )

							self.assertEqual(" ".join(self.get_from_offsets(outputs["word_offsets"]	, "word"    )    )	, outputs.text    )
							self.assertListEqual(self.get_from_offsets(outputs["word_offsets"]	, "word"    )	, ["<s>", "<s>", "</s>"]    )
							self.assertListEqual(self.get_from_offsets(outputs["word_offsets"]	, "start_offset"    )	, [0, 2, 4]    )
							self.assertListEqual(self.get_from_offsets(outputs["word_offsets"]	, "end_offset"    )	, [1, 3, 5]    )
				def       UpperCAmelCase      (		self    :			str    )	->	Dict:



							'''simple docstring'''



							a__  :	Tuple		 =			WavaVecaProcessorWithLM.from_pretrained("hf-internal-testing/processor_with_lm"    )
							a__  :	Union[str, Any]		 =			self._get_dummy_logits()

							a__  :	Union[str, Any]		 =			processor.batch_decode(a_	, output_word_offsets=a_    )

							# check Wav2Vec2CTCTokenizerOutput keys for word
							self.assertEqual(len(outputs.keys()    )	, 4    )
							self.assertTrue("text" in outputs    )
							self.assertTrue("word_offsets" in outputs    )
							self.assertTrue(isinstance(a_	, a_    )    )

							self.assertListEqual(
							    [" ".join(self.get_from_offsets(a_	, "word"    )    ) for o in outputs["word_offsets"]]	, outputs.text    )
							self.assertListEqual(self.get_from_offsets(outputs["word_offsets"][0]	, "word"    )	, ["<s>", "<s>", "</s>"]    )
							self.assertListEqual(self.get_from_offsets(outputs["word_offsets"][0]	, "start_offset"    )	, [0, 2, 4]    )
							self.assertListEqual(self.get_from_offsets(outputs["word_offsets"][0]	, "end_offset"    )	, [1, 3, 5]    )






				@slow
				@require_torch
				@require_torchaudio
				def       UpperCAmelCase      (		self    :			Union[str, Any]    )	->	Optional[Any]:



							'''simple docstring'''



							import torch

							a__  :	List[Any]		 =			load_dataset("common_voice"	, "en"	, split="train"	, streaming=a_    )
							a__  :	Optional[int]		 =			ds.cast_column("audio"	, datasets.Audio(sampling_rate=1_60_00    )    )
							a__  :	Optional[int]		 =			iter(a_    )
							a__  :	Optional[int]		 =			next(a_    )

							a__  :	Any		 =			AutoProcessor.from_pretrained("patrickvonplaten/wav2vec2-base-100h-with-lm"    )
							a__  :	Optional[Any]		 =			WavaVecaForCTC.from_pretrained("patrickvonplaten/wav2vec2-base-100h-with-lm"    )

							# compare to filename `common_voice_en_100038.mp3` of dataset viewer on https://huggingface.co/datasets/common_voice/viewer/en/train
							a__  :	int		 =			processor(sample["audio"]["array"]	, return_tensors="pt"    ).input_values

							with torch.no_grad():
										a__  :	int		 =			model(a_    ).logits.cpu().numpy()

							a__  :	str		 =			processor.decode(logits[0]	, output_word_offsets=a_    )

							a__  :	Optional[Any]		 =			model.config.inputs_to_logits_ratio / processor.feature_extractor.sampling_rate
							a__  :	Optional[Any]		 =			[
							    {
							        "start_time": d["start_offset"] * time_offset,
							        "end_time": d["end_offset"] * time_offset,
							        "word": d["word"],
							    }
							    for d in output["word_offsets"]
							]

							a__  :	List[str]		 =			"WHY DOES MILISANDRA LOOK LIKE SHE WANTS TO CONSUME JOHN SNOW ON THE RIVER AT THE WALL"

							# output words
							self.assertEqual(" ".join(self.get_from_offsets(a_	, "word"    )    )	, a_    )
							self.assertEqual(" ".join(self.get_from_offsets(a_	, "word"    )    )	, output.text    )

							# output times
							a__  :	Optional[Any]		 =			torch.tensor(self.get_from_offsets(a_	, "start_time"    )    )
							a__  :	str		 =			torch.tensor(self.get_from_offsets(a_	, "end_time"    )    )

							# fmt: off
							a__  :	Optional[int]		 =			torch.tensor([1.4199, 1.6599, 2.2599, 3.0, 3.24, 3.5999, 3.7999, 4.0999, 4.26, 4.94, 5.28, 5.6599, 5.78, 5.94, 6.32, 6.5399, 6.6599]    )
							a__  :	Optional[Any]		 =			torch.tensor([1.5399, 1.8999, 2.9, 3.16, 3.5399, 3.72, 4.0199, 4.1799, 4.76, 5.1599, 5.5599, 5.6999, 5.86, 6.1999, 6.38, 6.6199, 6.94]    )
							# fmt: on

							self.assertTrue(torch.allclose(a_	, a_	, atol=0.01    )    )
							self.assertTrue(torch.allclose(a_	, a_	, atol=0.01    )    )






"""simple docstring"""






def      lowercase__ (					lowerCAmelCase__   :			str			)    ->			list[int]:



			'''simple docstring'''
			a__  :	List[str]		 =			[0 for i in range(len(lowerCAmelCase__			)			)]

			# initialize interval's left pointer and right pointer
			a__ ,	a__  :	int		 =			0, 0

			for i in range(1							,			len(lowerCAmelCase__			)			):
						# case when current index is inside the interval
						if i <= right_pointer:
									a__  :	List[Any]		 =			min(right_pointer - i + 1							,			z_result[i - left_pointer]			)
									a__  :	List[str]		 =			min_edge

						while go_next(lowerCAmelCase__							,			lowerCAmelCase__							,			lowerCAmelCase__			):
									z_result[i] += 1

						# if new index's result gives us more right interval,
						# we've to update left_pointer and right_pointer
						if i + z_result[i] - 1 > right_pointer:
									a__ ,	a__  :	str		 =			i, i + z_result[i] - 1

			return z_result






def      lowercase__ (					lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			list[int]							,			lowerCAmelCase__   :			str			)    ->			bool:



			'''simple docstring'''
			return i + z_result[i] < len(lowerCAmelCase__			) and s[z_result[i]] == s[i + z_result[i]]






def      lowercase__ (					lowerCAmelCase__   :			str							,			lowerCAmelCase__   :			str			)    ->			int:



			'''simple docstring'''
			a__  :	List[Any]		 =			0
			# concatenate 'pattern' and 'input_str' and call z_function
			# with concatenated string
			a__  :	List[str]		 =			z_function(pattern + input_str			)

			for val in z_result:
						# if value is greater then length of the pattern string
						# that means this index is starting position of substring
						# which is equal to pattern string
						if val >= len(lowerCAmelCase__			):
									answer += 1

			return answer


if __name__ == "__main__":
		import doctest

		doctest.testmod()