


import functools
from typing import Any


def 		lowercase_	(  _UpperCamelCase							,      _UpperCamelCase	):


			'''simple docstring'''







			if not isinstance(_UpperCamelCase							,      _UpperCamelCase	) or len(_UpperCamelCase	) == 0:
						raise ValueError('''the string should be not empty string'''	)

			if not isinstance(_UpperCamelCase							,      _UpperCamelCase	) or not all(
			    isinstance(_UpperCamelCase							,      _UpperCamelCase	) and len(_UpperCamelCase	) > 0 for item in words	):
						raise ValueError('''the words should be a list of non-empty strings'''	)

			# Build trie
			__lowercase			       = {}
			__lowercase			       = '''WORD_KEEPER'''

			for word in words:
						__lowercase			       = trie
						for c in word:
									if c not in trie_node:
												__lowercase			       = {}

									__lowercase			       = trie_node[c]

						__lowercase			       = True

			__lowercase			       = len(_UpperCamelCase	)

			# Dynamic programming method
			@functools.cache
			def is_breakable(_UpperCamelCase	) -> bool:
						if index == len_string:
									return True

						__lowercase			       = trie
						for i in range(_UpperCamelCase							,      _UpperCamelCase	):
									__lowercase			       = trie_node.get(string[i]							,      _UpperCamelCase	)

									if trie_node is None:
												return False

									if trie_node.get(_UpperCamelCase							,      _UpperCamelCase	) and is_breakable(i + 1	):
												return True

						return False

			return is_breakable(0	)


if __name__ == "__main__":
	import doctest

	doctest.testmod()






import itertools
import random
import unittest

import numpy as np

from transformers import BatchFeature, SpeechTaFeatureExtractor
from transformers.testing_utils import require_torch
from transformers.utils.import_utils import is_torch_available

from ...test_sequence_feature_extraction_common import SequenceFeatureExtractionTestMixin


if is_torch_available():
	import torch


a			:			List[Any]												=					random.Random()


def 		lowercase_	(  _UpperCamelCase							,      _UpperCamelCase=1.0							,      _UpperCamelCase=None							,      _UpperCamelCase=None	):


			'''simple docstring'''







			if rng is None:
						__lowercase			       = global_rng

			__lowercase			       = []
			for batch_idx in range(shape[0]	):
						values.append([]	)
						for _ in range(shape[1]	):
									values[-1].append(rng.random() * scale	)

			return values
@require_torch
class 						lowerCamelCase_							(					unittest.TestCase					):



					'''simple docstring'''







					def __init__(					self			,							snake_case_			,							snake_case_=7			,							snake_case_=4_0_0			,							snake_case_=2_0_0_0			,							snake_case_=1			,							snake_case_=0.0			,							snake_case_=1_6_0_0_0			,							snake_case_=True			,							snake_case_=8_0			,							snake_case_=1_6			,							snake_case_=6_4			,							snake_case_="hann_window"			,							snake_case_=8_0			,							snake_case_=7_6_0_0			,							snake_case_=1e-1_0			,							snake_case_=True			,							) ->      Tuple:







								'''simple docstring'''

								__lowercase			       = parent
								__lowercase			       = batch_size
								__lowercase			       = min_seq_length
								__lowercase			       = max_seq_length
								__lowercase			       = (self.max_seq_length - self.min_seq_length) // (self.batch_size - 1)
								__lowercase			       = feature_size
								__lowercase			       = padding_value
								__lowercase			       = sampling_rate
								__lowercase			       = do_normalize
								__lowercase			       = num_mel_bins
								__lowercase			       = hop_length
								__lowercase			       = win_length
								__lowercase			       = win_function
								__lowercase			       = fmin
								__lowercase			       = fmax
								__lowercase			       = mel_floor
								__lowercase			       = return_attention_mask






					def A   (					self    ) ->      str:







								'''simple docstring'''

								return {
								    "feature_size": self.feature_size,
								    "padding_value": self.padding_value,
								    "sampling_rate": self.sampling_rate,
								    "do_normalize": self.do_normalize,
								    "num_mel_bins": self.num_mel_bins,
								    "hop_length": self.hop_length,
								    "win_length": self.win_length,
								    "win_function": self.win_function,
								    "fmin": self.fmin,
								    "fmax": self.fmax,
								    "mel_floor": self.mel_floor,
								    "return_attention_mask": self.return_attention_mask,
								}






					def A   (					self			,							snake_case_=False			,							snake_case_=False    ) ->      Tuple:







								'''simple docstring'''

								def _flatten(snake_case_    ):
											return list(itertools.chain(*snake_case_    )    )

								if equal_length:
											__lowercase			       = floats_list((self.batch_size, self.max_seq_length)    )
								else:
											# make sure that inputs increase in size
											__lowercase			       = [
											    _flatten(floats_list((x, self.feature_size)    )    )
											    for x in range(self.min_seq_length			,							self.max_seq_length			,							self.seq_length_diff    )
											]

								if numpify:
											__lowercase			       = [np.asarray(snake_case_    ) for x in speech_inputs]

								return speech_inputs






					def A   (					self			,							snake_case_=False			,							snake_case_=False    ) ->      Any:







								'''simple docstring'''

								if equal_length:
											__lowercase			       = [floats_list((self.max_seq_length, self.num_mel_bins)    ) for _ in range(self.batch_size    )]
								else:
											# make sure that inputs increase in size
											__lowercase			       = [
											    floats_list((x, self.num_mel_bins)    )
											    for x in range(self.min_seq_length			,							self.max_seq_length			,							self.seq_length_diff    )
											]

								if numpify:
											__lowercase			       = [np.asarray(snake_case_    ) for x in speech_inputs]

								return speech_inputs




@require_torch
class 						lowerCamelCase_							(					lowerCAmelCase__  ,  unittest.TestCase					):



					'''simple docstring'''







					__UpperCAmelCase							  =					SpeechTaFeatureExtractor






					def A   (					self    ) ->      Dict:







								'''simple docstring'''

								__lowercase			       = SpeechTaFeatureExtractionTester(self    )






					def A   (					self			,							snake_case_    ) ->      str:







								'''simple docstring'''

								self.assertTrue(np.all(np.mean(snake_case_			,							axis=0    ) < 1e-3    )    )
								self.assertTrue(np.all(np.abs(np.var(snake_case_			,							axis=0    ) - 1    ) < 1e-3    )    )






					def A   (					self    ) ->      int:







								'''simple docstring'''

								__lowercase			       = self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()    )
								# create three inputs of length 800, 1000, and 1200
								__lowercase			       = [floats_list((1, x)    )[0] for x in range(8_0_0			,							1_4_0_0			,							2_0_0    )]
								__lowercase			       = [np.asarray(snake_case_    ) for speech_input in speech_inputs]

								# Test not batched input
								__lowercase			       = feat_extract(speech_inputs[0]			,							return_tensors='''np'''    ).input_values
								__lowercase			       = feat_extract(np_speech_inputs[0]			,							return_tensors='''np'''    ).input_values
								self.assertTrue(np.allclose(snake_case_			,							snake_case_			,							atol=1e-3    )    )

								# Test batched
								__lowercase			       = feat_extract(snake_case_			,							return_tensors='''np'''    ).input_values
								__lowercase			       = feat_extract(snake_case_			,							return_tensors='''np'''    ).input_values
								for enc_seq_a, enc_seq_a in zip(snake_case_			,							snake_case_    ):
											self.assertTrue(np.allclose(snake_case_			,							snake_case_			,							atol=1e-3    )    )






					def A   (					self    ) ->      Any:







								'''simple docstring'''

								__lowercase			       = self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()    )
								__lowercase			       = [floats_list((1, x)    )[0] for x in range(8_0_0			,							1_4_0_0			,							2_0_0    )]

								__lowercase			       = ['''longest''', '''max_length''', '''do_not_pad''']
								__lowercase			       = [None, 1_6_0_0, None]
								for max_length, padding in zip(snake_case_			,							snake_case_    ):
											__lowercase			       = feat_extract(snake_case_			,							padding=snake_case_			,							max_length=snake_case_			,							return_tensors='''np'''    )
											__lowercase			       = processed.input_values

											self._check_zero_mean_unit_variance(input_values[0][:8_0_0]    )
											self.assertTrue(input_values[0][8_0_0:].sum() < 1e-6    )
											self._check_zero_mean_unit_variance(input_values[1][:1_0_0_0]    )
											self.assertTrue(input_values[0][1_0_0_0:].sum() < 1e-6    )
											self._check_zero_mean_unit_variance(input_values[2][:1_2_0_0]    )






					def A   (					self    ) ->      List[str]:







								'''simple docstring'''

								__lowercase			       = self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()    )
								__lowercase			       = range(8_0_0			,							1_4_0_0			,							2_0_0    )
								__lowercase			       = [floats_list((1, x)    )[0] for x in lengths]

								__lowercase			       = ['''longest''', '''max_length''', '''do_not_pad''']
								__lowercase			       = [None, 1_6_0_0, None]

								for max_length, padding in zip(snake_case_			,							snake_case_    ):
											__lowercase			       = feat_extract(snake_case_			,							max_length=snake_case_			,							padding=snake_case_    )
											__lowercase			       = processed.input_values

											self._check_zero_mean_unit_variance(input_values[0][:8_0_0]    )
											self._check_zero_mean_unit_variance(input_values[1][:1_0_0_0]    )
											self._check_zero_mean_unit_variance(input_values[2][:1_2_0_0]    )






					def A   (					self    ) ->      List[Any]:







								'''simple docstring'''

								__lowercase			       = self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()    )
								__lowercase			       = [floats_list((1, x)    )[0] for x in range(8_0_0			,							1_4_0_0			,							2_0_0    )]
								__lowercase			       = feat_extract(
								    snake_case_			,							truncation=snake_case_			,							max_length=1_0_0_0			,							padding='''max_length'''			,							return_tensors='''np'''    )
								__lowercase			       = processed.input_values

								self._check_zero_mean_unit_variance(input_values[0, :8_0_0]    )
								self._check_zero_mean_unit_variance(input_values[1]    )
								self._check_zero_mean_unit_variance(input_values[2]    )






					def A   (					self    ) ->      List[str]:







								'''simple docstring'''

								__lowercase			       = self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()    )
								__lowercase			       = [floats_list((1, x)    )[0] for x in range(8_0_0			,							1_4_0_0			,							2_0_0    )]
								__lowercase			       = feat_extract(
								    snake_case_			,							truncation=snake_case_			,							max_length=1_0_0_0			,							padding='''longest'''			,							return_tensors='''np'''    )
								__lowercase			       = processed.input_values

								self._check_zero_mean_unit_variance(input_values[0, :8_0_0]    )
								self._check_zero_mean_unit_variance(input_values[1, :1_0_0_0]    )
								self._check_zero_mean_unit_variance(input_values[2]    )

								# make sure that if max_length < longest -> then pad to max_length
								self.assertTrue(input_values.shape == (3, 1_0_0_0)    )

								__lowercase			       = [floats_list((1, x)    )[0] for x in range(8_0_0			,							1_4_0_0			,							2_0_0    )]
								__lowercase			       = feat_extract(
								    snake_case_			,							truncation=snake_case_			,							max_length=2_0_0_0			,							padding='''longest'''			,							return_tensors='''np'''    )
								__lowercase			       = processed.input_values

								self._check_zero_mean_unit_variance(input_values[0, :8_0_0]    )
								self._check_zero_mean_unit_variance(input_values[1, :1_0_0_0]    )
								self._check_zero_mean_unit_variance(input_values[2]    )

								# make sure that if max_length > longest -> then pad to longest
								self.assertTrue(input_values.shape == (3, 1_2_0_0)    )






					def A   (					self    ) ->      str:







								'''simple docstring'''

								__lowercase			       = self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()    )
								__lowercase			       = np.random.rand(1_0_0    ).astype(np.floataa    )
								__lowercase			       = np_speech_inputs.tolist()

								for inputs in [py_speech_inputs, np_speech_inputs]:
											__lowercase			       = feature_extractor.pad([{'''input_values''': inputs}]			,							return_tensors='''np'''    )
											self.assertTrue(np_processed.input_values.dtype == np.floataa    )
											__lowercase			       = feature_extractor.pad([{'''input_values''': inputs}]			,							return_tensors='''pt'''    )
											self.assertTrue(pt_processed.input_values.dtype == torch.floataa    )






					def A   (					self    ) ->      List[str]:







								'''simple docstring'''

								__lowercase			       = self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()    )
								# create three inputs of length 800, 1000, and 1200
								__lowercase			       = [floats_list((1, x)    )[0] for x in range(8_0_0			,							1_4_0_0			,							2_0_0    )]
								__lowercase			       = [np.asarray(snake_case_    ) for speech_input in speech_inputs]

								# Test feature size
								__lowercase			       = feature_extractor(audio_target=snake_case_			,							padding=snake_case_			,							return_tensors='''np'''    ).input_values
								self.assertTrue(input_values.ndim == 3    )
								self.assertTrue(input_values.shape[-1] == feature_extractor.num_mel_bins    )

								# Test not batched input
								__lowercase			       = feature_extractor(speech_inputs[0]			,							return_tensors='''np'''    ).input_values
								__lowercase			       = feature_extractor(np_speech_inputs[0]			,							return_tensors='''np'''    ).input_values
								self.assertTrue(np.allclose(snake_case_			,							snake_case_			,							atol=1e-3    )    )

								# Test batched
								__lowercase			       = feature_extractor(snake_case_			,							return_tensors='''np'''    ).input_values
								__lowercase			       = feature_extractor(snake_case_			,							return_tensors='''np'''    ).input_values
								for enc_seq_a, enc_seq_a in zip(snake_case_			,							snake_case_    ):
											self.assertTrue(np.allclose(snake_case_			,							snake_case_			,							atol=1e-3    )    )

								# Test 2-D numpy arrays are batched.
								__lowercase			       = [floats_list((1, x)    )[0] for x in (8_0_0, 8_0_0, 8_0_0)]
								__lowercase			       = np.asarray(snake_case_    )
								__lowercase			       = feature_extractor(snake_case_			,							return_tensors='''np'''    ).input_values
								__lowercase			       = feature_extractor(snake_case_			,							return_tensors='''np'''    ).input_values
								for enc_seq_a, enc_seq_a in zip(snake_case_			,							snake_case_    ):
											self.assertTrue(np.allclose(snake_case_			,							snake_case_			,							atol=1e-3    )    )






					def A   (					self    ) ->      Tuple:







								'''simple docstring'''

								__lowercase			       = self.feat_extract_tester.prepare_inputs_for_target()
								__lowercase			       = self.feature_extraction_class(**self.feat_extract_dict    )
								__lowercase			       = feat_extract.model_input_names[0]

								__lowercase			       = BatchFeature({input_name: speech_inputs}    )

								self.assertTrue(all(len(snake_case_    ) == len(snake_case_    ) for x, y in zip(snake_case_			,							processed_features[input_name]    )    )    )

								__lowercase			       = self.feat_extract_tester.prepare_inputs_for_target(equal_length=snake_case_    )
								__lowercase			       = BatchFeature({input_name: speech_inputs}			,							tensor_type='''np'''    )

								__lowercase			       = processed_features[input_name]

								if len(batch_features_input.shape    ) < 3:
											__lowercase			       = batch_features_input[:, :, None]

								self.assertTrue(
								    batch_features_input.shape
								    == (self.feat_extract_tester.batch_size, len(speech_inputs[0]    ), self.feat_extract_tester.num_mel_bins)    )






					@require_torch
					def A   (					self    ) ->      List[str]:







								'''simple docstring'''

								__lowercase			       = self.feat_extract_tester.prepare_inputs_for_target(equal_length=snake_case_    )
								__lowercase			       = self.feature_extraction_class(**self.feat_extract_dict    )
								__lowercase			       = feat_extract.model_input_names[0]

								__lowercase			       = BatchFeature({input_name: speech_inputs}			,							tensor_type='''pt'''    )

								__lowercase			       = processed_features[input_name]

								if len(batch_features_input.shape    ) < 3:
											__lowercase			       = batch_features_input[:, :, None]

								self.assertTrue(
								    batch_features_input.shape
								    == (self.feat_extract_tester.batch_size, len(speech_inputs[0]    ), self.feat_extract_tester.num_mel_bins)    )






					@require_torch
					def A   (					self    ) ->      Tuple:







								'''simple docstring'''

								__lowercase			       = self.feature_extraction_class(**self.feat_extract_dict    )
								__lowercase			       = self.feat_extract_tester.prepare_inputs_for_target()
								__lowercase			       = feat_extract.model_input_names[0]

								__lowercase			       = BatchFeature({input_name: speech_inputs}    )

								__lowercase			       = feat_extract.num_mel_bins  # hack!

								__lowercase			       = feat_extract.pad(snake_case_			,							padding='''longest'''			,							return_tensors='''np'''    )[input_name]
								__lowercase			       = feat_extract.pad(snake_case_			,							padding='''longest'''			,							return_tensors='''pt'''    )[input_name]

								self.assertTrue(abs(input_np.astype(np.floataa    ).sum() - input_pt.numpy().astype(np.floataa    ).sum()    ) < 1e-2    )






					def A   (					self    ) ->      Dict:







								'''simple docstring'''

								__lowercase			       = self.feat_extract_dict
								__lowercase			       = True
								__lowercase			       = self.feature_extraction_class(**snake_case_    )
								__lowercase			       = self.feat_extract_tester.prepare_inputs_for_target()
								__lowercase			       = [len(snake_case_    ) for x in speech_inputs]
								__lowercase			       = feat_extract.model_input_names[0]

								__lowercase			       = BatchFeature({input_name: speech_inputs}    )

								__lowercase			       = feat_extract.num_mel_bins  # hack!

								__lowercase			       = feat_extract.pad(snake_case_			,							padding='''longest'''			,							return_tensors='''np'''    )
								self.assertIn('''attention_mask'''			,							snake_case_    )
								self.assertListEqual(list(processed.attention_mask.shape    )			,							list(processed[input_name].shape[:2]    )    )
								self.assertListEqual(processed.attention_mask.sum(-1    ).tolist()			,							snake_case_    )






					def A   (					self    ) ->      Optional[Any]:







								'''simple docstring'''

								__lowercase			       = self.feat_extract_dict
								__lowercase			       = True
								__lowercase			       = self.feature_extraction_class(**snake_case_    )
								__lowercase			       = self.feat_extract_tester.prepare_inputs_for_target()
								__lowercase			       = [len(snake_case_    ) for x in speech_inputs]
								__lowercase			       = feat_extract.model_input_names[0]

								__lowercase			       = BatchFeature({input_name: speech_inputs}    )
								__lowercase			       = min(snake_case_    )

								__lowercase			       = feat_extract.num_mel_bins  # hack!

								__lowercase			       = feat_extract.pad(
								    snake_case_			,							padding='''max_length'''			,							max_length=snake_case_			,							truncation=snake_case_			,							return_tensors='''np'''    )
								self.assertIn('''attention_mask'''			,							snake_case_    )
								self.assertListEqual(
								    list(processed_pad.attention_mask.shape    )			,							[processed_pad[input_name].shape[0], max_length]    )
								self.assertListEqual(
								    processed_pad.attention_mask[:, :max_length].sum(-1    ).tolist()			,							[max_length for x in speech_inputs]    )






					def A   (					self			,							snake_case_    ) ->      str:







								'''simple docstring'''

								from datasets import load_dataset

								__lowercase			       = load_dataset('''hf-internal-testing/librispeech_asr_dummy'''			,							'''clean'''			,							split='''validation'''    )
								# automatic decoding with librispeech
								__lowercase			       = ds.sort('''id'''    ).select(range(snake_case_    )    )[:num_samples]['''audio''']

								return [x["array"] for x in speech_samples]






					def A   (					self    ) ->      Optional[int]:







								'''simple docstring'''

								__lowercase			       = torch.tensor(
								    [2.3_8_0_4e-0_3, 2.0_7_5_2e-0_3, 1.9_8_3_6e-0_3, 2.1_0_5_7e-0_3, 1.6_1_7_4e-0_3,
								     3.0_5_1_8e-0_4, 9.1_5_5_3e-0_5, 3.3_5_6_9e-0_4, 9.7_6_5_6e-0_4, 1.8_3_1_1e-0_3,
								     2.0_1_4_2e-0_3, 2.1_0_5_7e-0_3, 1.7_3_9_5e-0_3, 4.5_7_7_6e-0_4, -3.9_6_7_3e-0_4,
								     4.5_7_7_6e-0_4, 1.0_0_7_1e-0_3, 9.1_5_5_3e-0_5, 4.8_8_2_8e-0_4, 1.1_5_9_7e-0_3,
								     7.3_2_4_2e-0_4, 9.4_6_0_4e-0_4, 1.8_0_0_5e-0_3, 1.8_3_1_1e-0_3, 8.8_5_0_1e-0_4,
								     4.2_7_2_5e-0_4, 4.8_8_2_8e-0_4, 7.3_2_4_2e-0_4, 1.0_9_8_6e-0_3, 2.1_0_5_7e-0_3]    )
								# fmt: on

								__lowercase			       = self._load_datasamples(1    )
								__lowercase			       = SpeechTaFeatureExtractor()
								__lowercase			       = feature_extractor(snake_case_			,							return_tensors='''pt'''    ).input_values
								self.assertEquals(input_values.shape			,							(1, 9_3_6_8_0)    )
								self.assertTrue(torch.allclose(input_values[0, :3_0]			,							snake_case_			,							atol=1e-6    )    )






					def A   (					self    ) ->      str:







								'''simple docstring'''

								__lowercase			       = torch.tensor(
								    [-2.6_8_7_0, -3.0_1_0_4, -3.1_3_5_6, -3.5_3_5_2, -3.0_0_4_4, -3.0_3_5_3, -3.4_7_1_9, -3.6_7_7_7,
								     -3.1_5_2_0, -2.9_4_3_5, -2.6_5_5_3, -2.8_7_9_5, -2.9_9_4_4, -2.5_9_2_1, -3.0_2_7_9, -3.0_3_8_6,
								     -3.0_8_6_4, -3.1_2_9_1, -3.2_3_5_3, -2.7_4_4_4, -2.6_8_3_1, -2.7_2_8_7, -3.1_7_6_1, -3.1_5_7_1,
								     -3.2_7_2_6, -3.0_5_8_2, -3.1_0_0_7, -3.4_5_3_3, -3.4_6_9_5, -3.0_9_9_8]    )
								# fmt: on

								__lowercase			       = self._load_datasamples(1    )
								__lowercase			       = SpeechTaFeatureExtractor()
								__lowercase			       = feature_extractor(audio_target=snake_case_			,							return_tensors='''pt'''    ).input_values
								self.assertEquals(input_values.shape			,							(1, 3_6_6, 8_0)    )
								self.assertTrue(torch.allclose(input_values[0, 0, :3_0]			,							snake_case_			,							atol=1e-4    )    )


