
import unittest

from parameterized import parameterized

from transformers import LlamaConfig, is_torch_available, set_seed
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
      import torch

      from transformers import LlamaForCausalLM, LlamaForSequenceClassification, LlamaModel, LlamaTokenizer



class 		UpperCamelCase__  :
   def __init__(self :					Union[str, Any]					,				snake_case_ :					Union[str, Any]					,				snake_case_ :					Union[str, Any]=1_3					,				snake_case_ :					int=7					,				snake_case_ :					Any=True					,				snake_case_ :					List[str]=True					,				snake_case_ :					Optional[Any]=False					,				snake_case_ :					Optional[Any]=True					,				snake_case_ :					Tuple=9_9					,				snake_case_ :					Any=3_2					,				snake_case_ :					List[str]=5					,				snake_case_ :					Optional[int]=4					,				snake_case_ :					Optional[Any]=3_7					,				snake_case_ :					List[str]="gelu"					,				snake_case_ :					Optional[int]=0.1					,				snake_case_ :					List[Any]=0.1					,				snake_case_ :					List[str]=5_1_2					,				snake_case_ :					Dict=1_6					,				snake_case_ :					str=2					,				snake_case_ :					Tuple=0.02					,				snake_case_ :					List[Any]=3					,				snake_case_ :					int=4					,				snake_case_ :					Any=None					,				):
    __a :  Dict						=  parent
    __a :  List[str]						=  batch_size
    __a :  Optional[Any]						=  seq_length
    __a :  Dict						=  is_training
    __a :  List[Any]						=  use_input_mask
    __a :  Optional[Any]						=  use_token_type_ids
    __a :  List[str]						=  use_labels
    __a :  List[Any]						=  vocab_size
    __a :  Dict						=  hidden_size
    __a :  Union[str, Any]						=  num_hidden_layers
    __a :  Any						=  num_attention_heads
    __a :  Optional[int]						=  intermediate_size
    __a :  Dict						=  hidden_act
    __a :  List[Any]						=  hidden_dropout_prob
    __a :  Tuple						=  attention_probs_dropout_prob
    __a :  Optional[int]						=  max_position_embeddings
    __a :  str						=  type_vocab_size
    __a :  Any						=  type_sequence_label_size
    __a :  Any						=  initializer_range
    __a :  List[Any]						=  num_labels
    __a :  List[Any]						=  num_choices
    __a :  str						=  scope
   def       lowerCAmelCase			(self :					Dict   ):
    __a :  str						=  ids_tensor([self.batch_size, self.seq_length]					,				self.vocab_size   )

    __a :  Tuple						=  None
    if self.use_input_mask:
     __a :  List[str]						=  random_attention_mask([self.batch_size, self.seq_length]   )

    __a :  Any						=  None
    if self.use_token_type_ids:
     __a :  Union[str, Any]						=  ids_tensor([self.batch_size, self.seq_length]					,				self.type_vocab_size   )

    __a :  Tuple						=  None
    __a :  Dict						=  None
    __a :  List[Any]						=  None
    if self.use_labels:
     __a :  Dict						=  ids_tensor([self.batch_size]					,				self.type_sequence_label_size   )
     __a :  List[str]						=  ids_tensor([self.batch_size, self.seq_length]					,				self.num_labels   )
     __a :  Union[str, Any]						=  ids_tensor([self.batch_size]					,				self.num_choices   )

    __a :  str						=  self.get_config()

    return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels
   def       lowerCAmelCase			(self :					Tuple   ):
    return LlamaConfig(
        vocab_size=self.vocab_size					,				hidden_size=self.hidden_size					,				num_hidden_layers=self.num_hidden_layers					,				num_attention_heads=self.num_attention_heads					,				intermediate_size=self.intermediate_size					,				hidden_act=self.hidden_act					,				hidden_dropout_prob=self.hidden_dropout_prob					,				attention_probs_dropout_prob=self.attention_probs_dropout_prob					,				max_position_embeddings=self.max_position_embeddings					,				type_vocab_size=self.type_vocab_size					,				is_decoder=snake_case_					,				initializer_range=self.initializer_range					,				)
   def       lowerCAmelCase			(self :					str					,				snake_case_ :					Union[str, Any]					,				snake_case_ :					List[str]					,				snake_case_ :					Any					,				snake_case_ :					Dict					,				snake_case_ :					Optional[int]					,				snake_case_ :					int					,				snake_case_ :					int   ):
    __a :  Optional[int]						=  LlamaModel(config=snake_case_   )
    model.to(snake_case_   )
    model.eval()
    __a :  List[Any]						=  model(snake_case_					,				attention_mask=snake_case_   )
    __a :  List[Any]						=  model(snake_case_   )
    self.parent.assertEqual(result.last_hidden_state.shape					,				(self.batch_size, self.seq_length, self.hidden_size)   )
   def       lowerCAmelCase			(self :					Union[str, Any]					,				snake_case_ :					int					,				snake_case_ :					Optional[Any]					,				snake_case_ :					Dict					,				snake_case_ :					Optional[Any]					,				snake_case_ :					Optional[int]					,				snake_case_ :					Dict					,				snake_case_ :					List[Any]					,				snake_case_ :					List[Any]					,				snake_case_ :					List[Any]					,				):
    __a :  Optional[Any]						=  True
    __a :  Optional[int]						=  LlamaModel(snake_case_   )
    model.to(snake_case_   )
    model.eval()
    __a :  int						=  model(
        snake_case_					,				attention_mask=snake_case_					,				encoder_hidden_states=snake_case_					,				encoder_attention_mask=snake_case_					,				)
    __a :  Union[str, Any]						=  model(
        snake_case_					,				attention_mask=snake_case_					,				encoder_hidden_states=snake_case_					,				)
    __a :  str						=  model(snake_case_					,				attention_mask=snake_case_   )
    self.parent.assertEqual(result.last_hidden_state.shape					,				(self.batch_size, self.seq_length, self.hidden_size)   )
   def       lowerCAmelCase			(self :					List[str]					,				snake_case_ :					int					,				snake_case_ :					int					,				snake_case_ :					Dict					,				snake_case_ :					str					,				snake_case_ :					Tuple					,				snake_case_ :					Tuple					,				snake_case_ :					Optional[Any]					,				snake_case_ :					List[Any]					,				snake_case_ :					Tuple					,				):
    __a :  Any						=  LlamaForCausalLM(config=snake_case_   )
    model.to(snake_case_   )
    model.eval()
    __a :  Tuple						=  model(snake_case_					,				attention_mask=snake_case_					,				labels=snake_case_   )
    self.parent.assertEqual(result.logits.shape					,				(self.batch_size, self.seq_length, self.vocab_size)   )
   def       lowerCAmelCase			(self :					int					,				snake_case_ :					List[Any]					,				snake_case_ :					Optional[Any]					,				snake_case_ :					Any					,				snake_case_ :					Optional[Any]					,				snake_case_ :					Union[str, Any]					,				snake_case_ :					int					,				snake_case_ :					Any					,				snake_case_ :					Tuple					,				snake_case_ :					str					,				):
    __a :  List[str]						=  True
    __a :  Any						=  True
    __a :  Dict						=  LlamaForCausalLM(config=snake_case_   )
    model.to(snake_case_   )
    model.eval()

    # first forward pass
    __a :  int						=  model(
        snake_case_					,				attention_mask=snake_case_					,				encoder_hidden_states=snake_case_					,				encoder_attention_mask=snake_case_					,				use_cache=snake_case_					,				)
    __a :  Optional[Any]						=  outputs.past_key_values

    # create hypothetical multiple next token and extent to next_input_ids
    __a :  Any						=  ids_tensor((self.batch_size, 3)					,				config.vocab_size   )
    __a :  Tuple						=  ids_tensor((self.batch_size, 3)					,				vocab_size=2   )

    # append to next input_ids and
    __a :  Any						=  torch.cat([input_ids, next_tokens]					,				dim=-1   )
    __a :  Dict						=  torch.cat([input_mask, next_mask]					,				dim=-1   )

    __a :  Union[str, Any]						=  model(
        snake_case_					,				attention_mask=snake_case_					,				encoder_hidden_states=snake_case_					,				encoder_attention_mask=snake_case_					,				output_hidden_states=snake_case_					,				)['''hidden_states'''][0]
    __a :  Optional[int]						=  model(
        snake_case_					,				attention_mask=snake_case_					,				encoder_hidden_states=snake_case_					,				encoder_attention_mask=snake_case_					,				past_key_values=snake_case_					,				output_hidden_states=snake_case_					,				)['''hidden_states'''][0]

    # select random slice
    __a :  Tuple						=  ids_tensor((1,)					,				output_from_past.shape[-1]   ).item()
    __a :  str						=  output_from_no_past[:, -3:, random_slice_idx].detach()
    __a :  int						=  output_from_past[:, :, random_slice_idx].detach()

    self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]   )

    # test that outputs are equal for slice
    self.parent.assertTrue(torch.allclose(snake_case_					,				snake_case_					,				atol=1E-3   )   )







   def       lowerCAmelCase			(self :					str   ):
    __a :  Dict						=  self.prepare_config_and_inputs()
    (
        (
        __a
    )				,       (
        __a
    )				,       (
        __a
    )				,       (
        __a
    )				,       (
        __a
    )				,       (
        __a
    )				,       (
        __a
    )				,       
    ) :  List[str]						=  config_and_inputs
    __a :  Dict						=  {'''input_ids''': input_ids, '''attention_mask''': input_mask}
    return config, inputs_dict





@require_torch
class 		UpperCamelCase__  (       __lowercase    ,__lowercase    ,__lowercase    ,unittest.TestCase    ):
   _SCREAMING_SNAKE_CASE      :							Optional[Any]	       =      (LlamaModel, LlamaForCausalLM, LlamaForSequenceClassification) if is_torch_available() else ()
   _SCREAMING_SNAKE_CASE      :							Optional[Any]	       =      (LlamaForCausalLM,) if is_torch_available() else ()
   _SCREAMING_SNAKE_CASE      :							Optional[Any]	       =      (
       {
           "feature-extraction": LlamaModel,
           "text-classification": LlamaForSequenceClassification,
           "text-generation": LlamaForCausalLM,
           "zero-shot": LlamaForSequenceClassification,
       }
       if is_torch_available()
       else {}
   )
   _SCREAMING_SNAKE_CASE      :							Union[str, Any]	       =      False
   _SCREAMING_SNAKE_CASE      :							List[str]	       =      False
   def       lowerCAmelCase			(self :					Dict   ):
    __a :  Optional[Any]						=  LlamaModelTester(self   )
    __a :  Any						=  ConfigTester(self					,				config_class=snake_case_					,				hidden_size=3_7   )
   def       lowerCAmelCase			(self :					List[str]   ):
    self.config_tester.run_common_tests()
   def       lowerCAmelCase			(self :					int   ):
    __a :  int						=  self.model_tester.prepare_config_and_inputs()
    self.model_tester.create_and_check_model(*snake_case_   )
   def       lowerCAmelCase			(self :					List[Any]   ):
    __a :  Any						=  self.model_tester.prepare_config_and_inputs()
    for type in ["absolute", "relative_key", "relative_key_query"]:
     __a :  List[str]						=  type
     self.model_tester.create_and_check_model(*snake_case_   )
   def       lowerCAmelCase			(self :					List[Any]   ):
    __a				,       __a :  Union[str, Any]						=  self.model_tester.prepare_config_and_inputs_for_common()
    __a :  Any						=  3
    __a :  Any						=  input_dict['''input_ids''']
    __a :  Optional[Any]						=  input_ids.ne(1   ).to(snake_case_   )
    __a :  int						=  ids_tensor([self.model_tester.batch_size]					,				self.model_tester.type_sequence_label_size   )
    __a :  List[str]						=  LlamaForSequenceClassification(snake_case_   )
    model.to(snake_case_   )
    model.eval()
    __a :  Union[str, Any]						=  model(snake_case_					,				attention_mask=snake_case_					,				labels=snake_case_   )
    self.assertEqual(result.logits.shape					,				(self.model_tester.batch_size, self.model_tester.num_labels)   )
   def       lowerCAmelCase			(self :					str   ):
    __a				,       __a :  int						=  self.model_tester.prepare_config_and_inputs_for_common()
    __a :  List[str]						=  3
    __a :  Tuple						=  '''single_label_classification'''
    __a :  List[str]						=  input_dict['''input_ids''']
    __a :  int						=  input_ids.ne(1   ).to(snake_case_   )
    __a :  Tuple						=  ids_tensor([self.model_tester.batch_size]					,				self.model_tester.type_sequence_label_size   )
    __a :  Tuple						=  LlamaForSequenceClassification(snake_case_   )
    model.to(snake_case_   )
    model.eval()
    __a :  Optional[int]						=  model(snake_case_					,				attention_mask=snake_case_					,				labels=snake_case_   )
    self.assertEqual(result.logits.shape					,				(self.model_tester.batch_size, self.model_tester.num_labels)   )
   def       lowerCAmelCase			(self :					str   ):
    __a				,       __a :  Optional[Any]						=  self.model_tester.prepare_config_and_inputs_for_common()
    __a :  str						=  3
    __a :  Optional[int]						=  '''multi_label_classification'''
    __a :  Tuple						=  input_dict['''input_ids''']
    __a :  Union[str, Any]						=  input_ids.ne(1   ).to(snake_case_   )
    __a :  List[str]						=  ids_tensor(
        [self.model_tester.batch_size, config.num_labels]					,				self.model_tester.type_sequence_label_size   ).to(torch.float   )
    __a :  Tuple						=  LlamaForSequenceClassification(snake_case_   )
    model.to(snake_case_   )
    model.eval()
    __a :  Optional[int]						=  model(snake_case_					,				attention_mask=snake_case_					,				labels=snake_case_   )
    self.assertEqual(result.logits.shape					,				(self.model_tester.batch_size, self.model_tester.num_labels)   )
   @unittest.skip('''LLaMA buffers include complex numbers, which breaks this test'''   )
   def       lowerCAmelCase			(self :					Any   ):
    pass







   @parameterized.expand([('''linear''',), ('''dynamic''',)]   )
   def       lowerCAmelCase			(self :					Optional[Any]					,				snake_case_ :					Dict   ):
    __a				,       __a :  Dict						=  self.model_tester.prepare_config_and_inputs_for_common()
    __a :  Optional[int]						=  ids_tensor([1, 1_0]					,				config.vocab_size   )
    __a :  Tuple						=  ids_tensor([1, int(config.max_position_embeddings * 1.5   )]					,				config.vocab_size   )

    set_seed(4_2   )  # Fixed seed at init time so the two models get the same random weights
    __a :  str						=  LlamaModel(snake_case_   )
    original_model.to(snake_case_   )
    original_model.eval()
    __a :  Union[str, Any]						=  original_model(snake_case_   ).last_hidden_state
    __a :  List[Any]						=  original_model(snake_case_   ).last_hidden_state

    set_seed(4_2   )  # Fixed seed at init time so the two models get the same random weights
    __a :  Union[str, Any]						=  {'''type''': scaling_type, '''factor''': 10.0}
    __a :  Dict						=  LlamaModel(snake_case_   )
    scaled_model.to(snake_case_   )
    scaled_model.eval()
    __a :  Any						=  scaled_model(snake_case_   ).last_hidden_state
    __a :  Optional[Any]						=  scaled_model(snake_case_   ).last_hidden_state

    # Dynamic scaling does not change the RoPE embeddings until it receives an input longer than the original
    # maximum sequence length, so the outputs for the short input should match.
    if scaling_type == "dynamic":
     self.assertTrue(torch.allclose(snake_case_					,				snake_case_					,				atol=1E-5   )   )
    else:
     self.assertFalse(torch.allclose(snake_case_					,				snake_case_					,				atol=1E-5   )   )

    # The output should be different for long inputs
    self.assertFalse(torch.allclose(snake_case_					,				snake_case_					,				atol=1E-5   )   )





@require_torch
class 		UpperCamelCase__  (       unittest.TestCase    ):
   @unittest.skip('''Logits are not exactly the same, once we fix the instabalities somehow, will update!'''   )
   @slow
   def       lowerCAmelCase			(self :					int   ):
    __a :  Union[str, Any]						=  [1, 3_0_6, 4_6_5_8, 2_7_8, 6_5_9_3, 3_1_0, 2_8_3_4, 3_3_8]
    __a :  Any						=  LlamaForCausalLM.from_pretrained('''meta-llama/Llama-2-7b-hf'''					,				device_map='''auto'''   )
    __a :  List[str]						=  model(torch.tensor([input_ids]   )   )
    # Expected mean on dim = -1
    __a :  int						=  torch.tensor([[-6.6550, -4.1227, -4.9859, -3.2406, 0.8262, -3.0033, 1.2964, -3.3699]]   )
    torch.testing.assert_close(out.mean(-1   )					,				snake_case_					,				atol=1E-2					,				rtol=1E-2   )
    # slicing logits[0, 0, 0:30]
    # fmt: off
    __a :  Optional[Any]						=  torch.tensor([-12.8281, -7.4453, -0.4639, -8.0625, -7.2500, -8.0000, -6.4883, -7.7695, -7.8438, -7.0312, -6.2188, -7.1328, -1.8496, 1.9961, -8.6250, -6.7227, -12.8281, -6.9492, -7.0742, -7.7852, -7.5820, -7.9062, -6.9375, -7.9805, -8.3438, -8.1562, -8.0469, -7.6250, -7.7422, -7.3398,]   )
    # fmt: on
    torch.testing.assert_close(out[0, 0, :3_0]					,				snake_case_					,				atol=1E-5					,				rtol=1E-5   )
   @unittest.skip('''Logits are not exactly the same, once we fix the instabalities somehow, will update!'''   )
   @slow
   def       lowerCAmelCase			(self :					Optional[int]   ):
    __a :  Dict						=  [1, 3_0_6, 4_6_5_8, 2_7_8, 6_5_9_3, 3_1_0, 2_8_3_4, 3_3_8]
    __a :  List[str]						=  LlamaForCausalLM.from_pretrained('''meta-llama/Llama-2-13b-hf'''					,				device_map='''auto'''   )
    __a :  List[Any]						=  model(torch.tensor(snake_case_   )   )
    # Expected mean on dim = -1
    __a :  int						=  torch.tensor([[-2.0622, -1.2794, -1.1638, -0.9788, -1.4603, -1.0238, -1.7893, -1.4411]]   )
    torch.testing.assert_close(out.mean(-1   )					,				snake_case_					,				atol=1E-2					,				rtol=1E-2   )
    # slicing logits[0, 0, 0:30]
    # fmt: off
    __a :  Optional[Any]						=  torch.tensor([-8.1406, -8.0547, 2.7461, -1.2344, -0.1448, -1.8262, -1.0020, -1.8154, -1.6895, -1.8516, -2.3574, -0.9277, 3.7598, 6.5742, -1.2998, -0.1177, -8.1406, -2.9688, -2.9199, -3.1699, -3.5254, -2.3555, -2.7988, -3.4141, -2.8262, -4.5195, -3.3379, -3.3164, -2.7832, -3.0273]   )
    # fmt: on
    torch.testing.assert_close(out[0, 0, :3_0]					,				snake_case_					,				atol=1E-5					,				rtol=1E-5   )
   @unittest.skip('''Logits are not exactly the same, once we fix the instabalities somehow, will update!'''   )
   @slow
   def       lowerCAmelCase			(self :					Tuple   ):
    __a :  Any						=  [1, 3_0_6, 4_6_5_8, 2_7_8, 6_5_9_3, 3_1_0, 2_8_3_4, 3_3_8]
    __a :  List[Any]						=  LlamaForCausalLM.from_pretrained('''meta-llama/Llama-2-13b-chat-hf'''					,				device_map='''auto'''   )
    __a :  Optional[Any]						=  model(torch.tensor(snake_case_   )   )
    # Expected mean on dim = -1
    __a :  Union[str, Any]						=  torch.tensor([[-0.8562, -1.8520, -0.7551, -0.4162, -1.5161, -1.2038, -2.4823, -2.3254]]   )
    torch.testing.assert_close(out.mean(-1   )					,				snake_case_					,				atol=1E-2					,				rtol=1E-2   )
    # slicing logits[0, 0, 0:30]
    # fmt: off
    __a :  List[str]						=  torch.tensor([-2.2227, 4.8828, 0.9023, -0.4578, -0.7871, -0.1033, -0.6221, -0.5786, -0.7803, -1.0674, -1.2920, -0.1570, 0.8008, 2.0723, -0.9497, 0.2771, -2.2227, -0.7612, -1.4346, -1.2061, -1.6426, -0.3000, -0.7139, -1.1934, -1.8691, -1.6973, -1.5947, -1.2705, -0.3523, -0.5513]   )
    # fmt: on
    torch.testing.assert_close(out.mean(-1   )					,				snake_case_					,				atol=1E-2					,				rtol=1E-2   )
   @unittest.skip(
       '''Logits are not exactly the same, once we fix the instabalities somehow, will update! Also it is gonna be a `too_slow` test'''   )
   @slow
   def       lowerCAmelCase			(self :					Any   ):
    __a :  List[Any]						=  [1, 3_0_6, 4_6_5_8, 2_7_8, 6_5_9_3, 3_1_0, 2_8_3_4, 3_3_8]
    __a :  Union[str, Any]						=  LlamaForCausalLM.from_pretrained('''meta-llama/Llama-2-70b-hf'''					,				device_map='''auto'''   )
    __a :  Optional[int]						=  model(torch.tensor(snake_case_   )   )

    __a :  List[str]						=  torch.tensor(
        [[-4.2327, -3.3360, -4.6665, -4.7631, -1.8180, -3.4170, -1.4211, -3.1810]]					,				dtype=torch.floataa   )
    torch.testing.assert_close(out.mean(-1   )					,				snake_case_					,				atol=1E-2					,				rtol=1E-2   )
    # fmt: off
    __a :  List[Any]						=  torch.tensor([-9.4922, -3.9551, 1.7998, -5.6758, -5.1055, -5.8984, -4.8320, -6.8086, -6.5391, -5.6172, -5.5820, -5.5352, 1.7881, 3.6289, -6.5117, -3.4785, -9.5000, -6.0352, -6.8125, -6.0195, -6.6836, -5.4727, -6.2812, -6.0391, -7.3398, -7.4297, -7.4844, -6.5820, -5.8789, -5.5312]   )
    # fmt: on
    torch.testing.assert_close(out[0, 0, :3_0]					,				snake_case_					,				atol=1E-5					,				rtol=1E-5   )







   @unittest.skip('''Model is curently gated'''   )
   @slow
   def       lowerCAmelCase			(self :					Any   ):
    __a :  List[Any]						=  '''Simply put, the theory of relativity states that 1) the laws of physics are the same everywhere in the universe and 2) the passage of time and the length of objects can vary depending on the observer\'s frame of reference.\n\nThe first part of the theory, that the laws of physics are the same everywhere, is known as the "princi'''
    __a :  List[Any]						=  '''Simply put, the theory of relativity states that '''
    __a :  List[Any]						=  LlamaTokenizer.from_pretrained('''meta-llama/Llama-2-13b-chat-hf'''   )
    __a :  int						=  tokenizer.encode(snake_case_					,				return_tensors='''pt'''   )
    __a :  List[Any]						=  LlamaForCausalLM.from_pretrained(
        '''meta-llama/Llama-2-13b-chat-hf'''					,				device_map='''sequential'''					,				use_safetensors=snake_case_   )

    # greedy generation outputs
    __a :  Optional[int]						=  model.generate(snake_case_					,				max_new_tokens=6_4					,				top_p=snake_case_					,				temperature=1					,				do_sample=snake_case_   )
    __a :  Union[str, Any]						=  tokenizer.decode(generated_ids[0]					,				skip_special_tokens=snake_case_   )
    self.assertEqual(snake_case_					,				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'))
