
import gc
import unittest

from transformers import MODEL_FOR_MASKED_LM_MAPPING, TF_MODEL_FOR_MASKED_LM_MAPPING, FillMaskPipeline, pipeline
from transformers.pipelines import PipelineException
from transformers.testing_utils import (
    is_pipeline_test,
    is_torch_available,
    nested_simplify,
    require_tf,
    require_torch,
    require_torch_gpu,
    slow,
)

from .test_pipelines_common import ANY



@is_pipeline_test
class 		UpperCamelCase__  (       unittest.TestCase    ):
   _SCREAMING_SNAKE_CASE      :							Any	       =      MODEL_FOR_MASKED_LM_MAPPING
   _SCREAMING_SNAKE_CASE      :							Optional[Any]	       =      TF_MODEL_FOR_MASKED_LM_MAPPING
   def       lowerCAmelCase			(self :					Tuple   ):
    super().tearDown()
    # clean-up as much as possible GPU memory occupied by PyTorch
    gc.collect()
    if is_torch_available():
     import torch

     torch.cuda.empty_cache()
   @require_tf
   def       lowerCAmelCase			(self :					List[str]   ):
    __a :  List[str]						=  pipeline(task='''fill-mask'''					,				model='''sshleifer/tiny-distilroberta-base'''					,				top_k=2					,				framework='''tf'''   )
    __a :  int						=  unmasker('''My name is <mask>'''   )
    self.assertEqual(
        nested_simplify(snake_case_					,				decimals=6   )					,				[
            {'''sequence''': '''My name is grouped''', '''score''': 2.1E-05, '''token''': 3_8_0_1_5, '''token_str''': ''' grouped'''},
            {'''sequence''': '''My name is accuser''', '''score''': 2.1E-05, '''token''': 2_5_5_0_6, '''token_str''': ''' accuser'''},
        ]					,				)

    __a :  Tuple						=  unmasker('''The largest city in France is <mask>'''   )
    self.assertEqual(
        nested_simplify(snake_case_					,				decimals=6   )					,				[
            {
                '''sequence''': '''The largest city in France is grouped''',
                '''score''': 2.1E-05,
                '''token''': 3_8_0_1_5,
                '''token_str''': ''' grouped''',
            },
            {
                '''sequence''': '''The largest city in France is accuser''',
                '''score''': 2.1E-05,
                '''token''': 2_5_5_0_6,
                '''token_str''': ''' accuser''',
            },
        ]					,				)

    __a :  Optional[int]						=  unmasker('''My name is <mask>'''					,				targets=[''' Patrick''', ''' Clara''', ''' Teven''']					,				top_k=3   )
    self.assertEqual(
        nested_simplify(snake_case_					,				decimals=6   )					,				[
            {'''sequence''': '''My name is Clara''', '''score''': 2E-05, '''token''': 1_3_6_0_6, '''token_str''': ''' Clara'''},
            {'''sequence''': '''My name is Patrick''', '''score''': 2E-05, '''token''': 3_4_9_9, '''token_str''': ''' Patrick'''},
            {'''sequence''': '''My name is Te''', '''score''': 1.9E-05, '''token''': 2_9_4_1, '''token_str''': ''' Te'''},
        ]					,				)
   @require_torch
   def       lowerCAmelCase			(self :					Any   ):
    __a :  Optional[Any]						=  pipeline(task='''fill-mask'''					,				model='''sshleifer/tiny-distilroberta-base'''					,				top_k=2					,				framework='''pt'''   )

    __a :  Dict						=  unmasker('''My name is <mask>'''   )
    self.assertEqual(
        nested_simplify(snake_case_					,				decimals=6   )					,				[
            {'''sequence''': '''My name is Maul''', '''score''': 2.2E-05, '''token''': 3_5_6_7_6, '''token_str''': ''' Maul'''},
            {'''sequence''': '''My name isELS''', '''score''': 2.2E-05, '''token''': 1_6_4_1_6, '''token_str''': '''ELS'''},
        ]					,				)

    __a :  List[Any]						=  unmasker('''The largest city in France is <mask>'''   )
    self.assertEqual(
        nested_simplify(snake_case_					,				decimals=6   )					,				[
            {
                '''sequence''': '''The largest city in France is Maul''',
                '''score''': 2.2E-05,
                '''token''': 3_5_6_7_6,
                '''token_str''': ''' Maul''',
            },
            {'''sequence''': '''The largest city in France isELS''', '''score''': 2.2E-05, '''token''': 1_6_4_1_6, '''token_str''': '''ELS'''},
        ]					,				)

    __a :  Tuple						=  unmasker('''My name is <mask>'''					,				targets=[''' Patrick''', ''' Clara''', ''' Teven''']					,				top_k=3   )
    self.assertEqual(
        nested_simplify(snake_case_					,				decimals=6   )					,				[
            {'''sequence''': '''My name is Patrick''', '''score''': 2.1E-05, '''token''': 3_4_9_9, '''token_str''': ''' Patrick'''},
            {'''sequence''': '''My name is Te''', '''score''': 2E-05, '''token''': 2_9_4_1, '''token_str''': ''' Te'''},
            {'''sequence''': '''My name is Clara''', '''score''': 2E-05, '''token''': 1_3_6_0_6, '''token_str''': ''' Clara'''},
        ]					,				)

    __a :  int						=  unmasker('''My name is <mask> <mask>'''					,				top_k=2   )

    self.assertEqual(
        nested_simplify(snake_case_					,				decimals=6   )					,				[
            [
                {
                    '''score''': 2.2E-05,
                    '''token''': 3_5_6_7_6,
                    '''token_str''': ''' Maul''',
                    '''sequence''': '''<s>My name is Maul<mask></s>''',
                },
                {'''score''': 2.2E-05, '''token''': 1_6_4_1_6, '''token_str''': '''ELS''', '''sequence''': '''<s>My name isELS<mask></s>'''},
            ],
            [
                {
                    '''score''': 2.2E-05,
                    '''token''': 3_5_6_7_6,
                    '''token_str''': ''' Maul''',
                    '''sequence''': '''<s>My name is<mask> Maul</s>''',
                },
                {'''score''': 2.2E-05, '''token''': 1_6_4_1_6, '''token_str''': '''ELS''', '''sequence''': '''<s>My name is<mask>ELS</s>'''},
            ],
        ]					,				)
   @require_torch_gpu
   def       lowerCAmelCase			(self :					Any   ):
    __a :  int						=  pipeline('''fill-mask'''					,				model='''hf-internal-testing/tiny-random-distilbert'''					,				device=0					,				framework='''pt'''   )

    # convert model to fp16
    pipe.model.half()

    __a :  Tuple						=  pipe('''Paris is the [MASK] of France.'''   )
    # We actually don't care about the result, we just want to make sure
    # it works, meaning the float16 tensor got casted back to float32
    # for postprocessing.
    self.assertIsInstance(snake_case_					,				snake_case_   )
   @slow
   @require_torch
   def       lowerCAmelCase			(self :					Tuple   ):
    __a :  List[Any]						=  pipeline(task='''fill-mask'''					,				model='''distilroberta-base'''					,				top_k=2					,				framework='''pt'''   )
    self.run_large_test(snake_case_   )
   @slow
   @require_tf
   def       lowerCAmelCase			(self :					Optional[int]   ):
    __a :  Tuple						=  pipeline(task='''fill-mask'''					,				model='''distilroberta-base'''					,				top_k=2					,				framework='''tf'''   )
    self.run_large_test(snake_case_   )
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					Any   ):
    __a :  Union[str, Any]						=  unmasker('''My name is <mask>'''   )
    self.assertEqual(
        nested_simplify(snake_case_   )					,				[
            {'''sequence''': '''My name is John''', '''score''': 0.008, '''token''': 6_1_0, '''token_str''': ''' John'''},
            {'''sequence''': '''My name is Chris''', '''score''': 0.007, '''token''': 1_5_7_3, '''token_str''': ''' Chris'''},
        ]					,				)
    __a :  int						=  unmasker('''The largest city in France is <mask>'''   )
    self.assertEqual(
        nested_simplify(snake_case_   )					,				[
            {
                '''sequence''': '''The largest city in France is Paris''',
                '''score''': 0.251,
                '''token''': 2_2_0_1,
                '''token_str''': ''' Paris''',
            },
            {
                '''sequence''': '''The largest city in France is Lyon''',
                '''score''': 0.214,
                '''token''': 1_2_7_9_0,
                '''token_str''': ''' Lyon''',
            },
        ]					,				)

    __a :  Optional[Any]						=  unmasker('''My name is <mask>'''					,				targets=[''' Patrick''', ''' Clara''', ''' Teven''']					,				top_k=3   )
    self.assertEqual(
        nested_simplify(snake_case_   )					,				[
            {'''sequence''': '''My name is Patrick''', '''score''': 0.005, '''token''': 3_4_9_9, '''token_str''': ''' Patrick'''},
            {'''sequence''': '''My name is Clara''', '''score''': 0.000, '''token''': 1_3_6_0_6, '''token_str''': ''' Clara'''},
            {'''sequence''': '''My name is Te''', '''score''': 0.000, '''token''': 2_9_4_1, '''token_str''': ''' Te'''},
        ]					,				)
   @require_torch
   def       lowerCAmelCase			(self :					List[Any]   ):
    __a :  Optional[Any]						=  pipeline(task='''fill-mask'''					,				model='''sshleifer/tiny-distilroberta-base'''					,				framework='''pt'''   )
    __a :  Optional[int]						=  None
    __a :  Optional[int]						=  None
    self.run_pipeline_test(snake_case_					,				[]   )
   @require_tf
   def       lowerCAmelCase			(self :					str   ):
    __a :  Union[str, Any]						=  pipeline(task='''fill-mask'''					,				model='''sshleifer/tiny-distilroberta-base'''					,				framework='''tf'''   )
    __a :  List[Any]						=  None
    __a :  str						=  None
    self.run_pipeline_test(snake_case_					,				[]   )
   def       lowerCAmelCase			(self :					Dict					,				snake_case_ :					Any					,				snake_case_ :					Optional[int]					,				snake_case_ :					int   ):
    if tokenizer is None or tokenizer.mask_token_id is None:
     self.skipTest('''The provided tokenizer has no mask token, (probably reformer or wav2vec2)'''   )

    __a :  Any						=  FillMaskPipeline(model=snake_case_					,				tokenizer=snake_case_   )
    __a :  List[str]						=  [
        f"This is another {tokenizer.mask_token} test",
    ]
    return fill_masker, examples
   def       lowerCAmelCase			(self :					Optional[Any]					,				snake_case_ :					Union[str, Any]					,				snake_case_ :					Any   ):
    __a :  List[Any]						=  fill_masker.tokenizer
    __a :  int						=  fill_masker.model

    __a :  Optional[Any]						=  fill_masker(
        f"This is a {tokenizer.mask_token}"					,				)
    self.assertEqual(
        snake_case_					,				[
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
        ]					,				)

    __a :  Tuple						=  fill_masker([f"This is a {tokenizer.mask_token}"]   )
    self.assertEqual(
        snake_case_					,				[
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
        ]					,				)

    __a :  List[Any]						=  fill_masker([f"This is a {tokenizer.mask_token}", f"Another {tokenizer.mask_token} great test."]   )
    self.assertEqual(
        snake_case_					,				[
            [
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            ],
            [
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            ],
        ]					,				)

    with self.assertRaises(snake_case_   ):
     fill_masker([None]   )
    # No mask_token is not supported
    with self.assertRaises(snake_case_   ):
     fill_masker('''This is'''   )

    self.run_test_top_k(snake_case_					,				snake_case_   )
    self.run_test_targets(snake_case_					,				snake_case_   )
    self.run_test_top_k_targets(snake_case_					,				snake_case_   )
    self.fill_mask_with_duplicate_targets_and_top_k(snake_case_					,				snake_case_   )
    self.fill_mask_with_multiple_masks(snake_case_					,				snake_case_   )
   def       lowerCAmelCase			(self :					Optional[int]					,				snake_case_ :					Any					,				snake_case_ :					Optional[Any]   ):
    __a :  List[str]						=  tokenizer.get_vocab()
    __a :  Optional[Any]						=  sorted(vocab.keys()   )[:2]
    # Pipeline argument
    __a :  Any						=  FillMaskPipeline(model=snake_case_					,				tokenizer=snake_case_					,				targets=snake_case_   )
    __a :  Any						=  fill_masker(f"This is a {tokenizer.mask_token}"   )
    self.assertEqual(
        snake_case_					,				[
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
        ]					,				)
    __a :  List[str]						=  {vocab[el] for el in targets}
    self.assertEqual({el['''token'''] for el in outputs}					,				snake_case_   )
    __a :  str						=  [tokenizer.decode([x]   ) for x in target_ids]
    self.assertEqual({el['''token_str'''] for el in outputs}					,				set(snake_case_   )   )

    # Call argument
    __a :  Any						=  FillMaskPipeline(model=snake_case_					,				tokenizer=snake_case_   )
    __a :  Tuple						=  fill_masker(f"This is a {tokenizer.mask_token}"					,				targets=snake_case_   )
    self.assertEqual(
        snake_case_					,				[
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
        ]					,				)
    __a :  Optional[int]						=  {vocab[el] for el in targets}
    self.assertEqual({el['''token'''] for el in outputs}					,				snake_case_   )
    __a :  str						=  [tokenizer.decode([x]   ) for x in target_ids]
    self.assertEqual({el['''token_str'''] for el in outputs}					,				set(snake_case_   )   )

    # Score equivalence
    __a :  Dict						=  fill_masker(f"This is a {tokenizer.mask_token}"					,				targets=snake_case_   )
    __a :  List[Any]						=  [top_mask['''token_str'''] for top_mask in outputs]
    __a :  Dict						=  [top_mask['''score'''] for top_mask in outputs]

    # For some BPE tokenizers, `</w>` is removed during decoding, so `token_str` won't be the same as in `targets`.
    if set(snake_case_   ) == set(snake_case_   ):
     __a :  Dict						=  fill_masker(f"This is a {tokenizer.mask_token}"					,				targets=snake_case_   )
     __a :  int						=  [top_mask['''score'''] for top_mask in unmasked_targets]
     self.assertEqual(nested_simplify(snake_case_   )					,				nested_simplify(snake_case_   )   )

    # Raises with invalid
    with self.assertRaises(snake_case_   ):
     __a :  Union[str, Any]						=  fill_masker(f"This is a {tokenizer.mask_token}"					,				targets=[]   )
    # For some tokenizers, `""` is actually in the vocabulary and the expected error won't raised
    if "" not in tokenizer.get_vocab():
     with self.assertRaises(snake_case_   ):
      __a :  Any						=  fill_masker(f"This is a {tokenizer.mask_token}"					,				targets=['''''']   )
     with self.assertRaises(snake_case_   ):
      __a :  str						=  fill_masker(f"This is a {tokenizer.mask_token}"					,				targets=''''''   )
   def       lowerCAmelCase			(self :					List[Any]					,				snake_case_ :					List[Any]					,				snake_case_ :					Union[str, Any]   ):
    __a :  Any						=  FillMaskPipeline(model=snake_case_					,				tokenizer=snake_case_					,				top_k=2   )
    __a :  Any						=  fill_masker(f"This is a {tokenizer.mask_token}"   )
    self.assertEqual(
        snake_case_					,				[
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
        ]					,				)

    __a :  Union[str, Any]						=  FillMaskPipeline(model=snake_case_					,				tokenizer=snake_case_   )
    __a :  List[Any]						=  fill_masker(f"This is a {tokenizer.mask_token}"					,				top_k=2   )
    self.assertEqual(
        snake_case_					,				[
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
        ]					,				)
    self.assertEqual(nested_simplify(snake_case_   )					,				nested_simplify(snake_case_   )   )
   def       lowerCAmelCase			(self :					Tuple					,				snake_case_ :					Tuple					,				snake_case_ :					int   ):
    __a :  str						=  tokenizer.get_vocab()
    __a :  Dict						=  FillMaskPipeline(model=snake_case_					,				tokenizer=snake_case_   )

    # top_k=2, ntargets=3
    __a :  Optional[Any]						=  sorted(vocab.keys()   )[:3]
    __a :  Optional[Any]						=  fill_masker(f"This is a {tokenizer.mask_token}"					,				top_k=2					,				targets=snake_case_   )

    # If we use the most probably targets, and filter differently, we should still
    # have the same results
    __a :  str						=  [el['''token_str'''] for el in sorted(snake_case_					,				key=lambda snake_case_   : x["score"]					,				reverse=snake_case_   )]
    # For some BPE tokenizers, `</w>` is removed during decoding, so `token_str` won't be the same as in `targets`.
    if set(snake_case_   ).issubset(snake_case_   ):
     __a :  Optional[Any]						=  fill_masker(f"This is a {tokenizer.mask_token}"					,				top_k=3					,				targets=snake_case_   )
     # They should yield exactly the same result
     self.assertEqual(nested_simplify(snake_case_   )					,				nested_simplify(snake_case_   )   )
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					str					,				snake_case_ :					List[str]   ):
    __a :  Tuple						=  FillMaskPipeline(model=snake_case_					,				tokenizer=snake_case_   )
    __a :  int						=  tokenizer.get_vocab()
    # String duplicates + id duplicates
    __a :  Optional[int]						=  sorted(vocab.keys()   )[:3]
    __a :  Optional[int]						=  [targets[0], targets[1], targets[0], targets[2], targets[1]]
    __a :  int						=  fill_masker(f"My name is {tokenizer.mask_token}"					,				targets=snake_case_					,				top_k=1_0   )

    # The target list contains duplicates, so we can't output more
    # than them
    self.assertEqual(len(snake_case_   )					,				3   )







   def       lowerCAmelCase			(self :					Union[str, Any]					,				snake_case_ :					Tuple					,				snake_case_ :					Union[str, Any]   ):
    __a :  Any						=  FillMaskPipeline(model=snake_case_					,				tokenizer=snake_case_   )

    __a :  List[str]						=  fill_masker(
        f"This is a {tokenizer.mask_token} {tokenizer.mask_token} {tokenizer.mask_token}"					,				top_k=2   )
    self.assertEqual(
        snake_case_					,				[
            [
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            ],
            [
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            ],
            [
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
                {'''sequence''': ANY(snake_case_   ), '''score''': ANY(snake_case_   ), '''token''': ANY(snake_case_   ), '''token_str''': ANY(snake_case_   )},
            ],
        ]					,				)


def    __UpperCamelCase     (				lowerCAmelCase__							:				str  ,   lowerCAmelCase__							:				str  ):
 __a :  str						=  len(lowerCAmelCase__  )
 __a :  Optional[int]						=  []
 for i in range(len(lowerCAmelCase__  ) - pat_len + 1  ):
  __a :  str						=  True
  for j in range(lowerCAmelCase__  ):
   if s[i + j] != pattern[j]:
    __a :  Tuple						=  False
    break
  if match_found:
   position.append(lowerCAmelCase__  )
 return position


if __name__ == "__main__":
      assert naive_pattern_search('ABCDEFG', 'DE') == [3]
      print(naive_pattern_search('ABAAABCDBBABCDDEBCABC', 'ABC'))
