






'''simple docstring'''

import torch
from torch import nn
from torch.nn import CrossEntropyLoss, MSELoss

from transformers.file_utils import add_start_docstrings, add_start_docstrings_to_model_forward
from transformers.models.bert.modeling_bert import (
    BERT_INPUTS_DOCSTRING,
    BERT_START_DOCSTRING,
    BertEmbeddings,
    BertLayer,
    BertPooler,
    BertPreTrainedModel,
)
def     __lowercase  (_lowercase     )   ->     str:


     """simple docstring"""
     __lowerCamelCase						:       Optional[Any]				   =				torch.exp(_lowercase     )
     __lowerCamelCase						:       Dict				   =				torch.sum(_lowercase,						dim=1     )  # sum of exp(x_i)
     __lowerCamelCase						:       int				   =				torch.sum(x * exp_x,						dim=1     )  # sum of x_i * exp(x_i)
     return torch.log(_lowercase     ) - B / A







class 	SCREAMING_SNAKE_CASE	(      nn.Module  ):




       def __init__(					self      : List[Any]	,    A__      : Any					):


            """simple docstring"""







            super().__init__()
            __lowerCamelCase						:       Optional[int]				   =				config.output_attentions
            __lowerCamelCase						:       Optional[int]				   =				config.output_hidden_states
            __lowerCamelCase						:       Optional[int]				   =				nn.ModuleList([BertLayer(A__					) for _ in range(config.num_hidden_layers					)]					)
            __lowerCamelCase						:       Optional[Any]				   =				nn.ModuleList([BertHighway(A__					) for _ in range(config.num_hidden_layers					)]					)

            __lowerCamelCase						:       Optional[Any]				   =				[-1 for _ in range(config.num_hidden_layers					)]




       def 					a_					(					self      : List[Any]	,    A__      : Union[str, Any]					):


            """simple docstring"""







            if (type(A__					) is float) or (type(A__					) is int):
                 for i in range(len(self.early_exit_entropy					)					):
                      __lowerCamelCase						:       List[Any]				   =				x
            else:
                 __lowerCamelCase						:       List[str]				   =				x




       def 					a_					(					self      : str	,    A__      : int					):


            """simple docstring"""







            __lowerCamelCase						:       int				   =				pooler.state_dict()
            for highway in self.highway:
                 for name, param in highway.pooler.state_dict().items():
                      param.copy_(loaded_model[name]					)




       def 					a_					(					self      : str	,    A__      : Union[str, Any]	,    A__      : str=None	,    A__      : Tuple=None	,    A__      : str=None	,    A__      : Tuple=None	,    ):


            """simple docstring"""







            __lowerCamelCase						:       Any				   =				()
            __lowerCamelCase						:       Union[str, Any]				   =				()
            __lowerCamelCase						:       Optional[Any]				   =				()
            for i, layer_module in enumerate(self.layer					):
                 if self.output_hidden_states:
                      __lowerCamelCase						:       Optional[int]				   =				all_hidden_states + (hidden_states,)

                 __lowerCamelCase						:       str				   =				layer_module(
                     A__	,    A__	,    head_mask[i]	,    A__	,    A__					)
                 __lowerCamelCase						:       Dict				   =				layer_outputs[0]

                 if self.output_attentions:
                      __lowerCamelCase						:       Optional[Any]				   =				all_attentions + (layer_outputs[1],)

                 __lowerCamelCase						:       Any				   =				(hidden_states,)
                 if self.output_hidden_states:
                      __lowerCamelCase						:       Dict				   =				current_outputs + (all_hidden_states,)
                 if self.output_attentions:
                      __lowerCamelCase						:       Optional[int]				   =				current_outputs + (all_attentions,)

                 __lowerCamelCase						:       str				   =				self.highway[i](A__					)
                 # logits, pooled_output

                 if not self.training:
                      __lowerCamelCase						:       Any				   =				highway_exit[0]
                      __lowerCamelCase						:       List[str]				   =				entropy(A__					)
                      __lowerCamelCase						:       Optional[Any]				   =				highway_exit + (highway_entropy,)  # logits, hidden_states(?), entropy
                      __lowerCamelCase						:       Tuple				   =				all_highway_exits + (highway_exit,)

                      if highway_entropy < self.early_exit_entropy[i]:
                           __lowerCamelCase						:       str				   =				(highway_logits,) + current_outputs[1:] + (all_highway_exits,)
                           raise HighwayException(A__	,    i + 1					)
                 else:
                      __lowerCamelCase						:       Optional[int]				   =				all_highway_exits + (highway_exit,)

        # Add last layer
            if self.output_hidden_states:
                 __lowerCamelCase						:       Union[str, Any]				   =				all_hidden_states + (hidden_states,)

            __lowerCamelCase						:       int				   =				(hidden_states,)
            if self.output_hidden_states:
                 __lowerCamelCase						:       Optional[int]				   =				outputs + (all_hidden_states,)
            if self.output_attentions:
                 __lowerCamelCase						:       List[str]				   =				outputs + (all_attentions,)

            __lowerCamelCase						:       Tuple				   =				outputs + (all_highway_exits,)
            return outputs  # last-layer hidden state, (all hidden states), (all attentions), all highway exits







@add_start_docstrings(
    'The Bert Model transformer with early exiting (DeeBERT). '    ,   lowerCAmelCase_    ,   )
class 	SCREAMING_SNAKE_CASE	(      lowerCAmelCase_  ):




       def __init__(					self      : Optional[int]	,    A__      : Dict					):


            """simple docstring"""







            super().__init__(A__					)
            __lowerCamelCase						:       Dict				   =				config

            __lowerCamelCase						:       Union[str, Any]				   =				BertEmbeddings(A__					)
            __lowerCamelCase						:       Any				   =				DeeBertEncoder(A__					)
            __lowerCamelCase						:       List[Any]				   =				BertPooler(A__					)

            self.init_weights()




       def 					a_					(					self      : str					):


            """simple docstring"""







            self.encoder.init_highway_pooler(self.pooler					)




       def 					a_					(					self      : Dict					):


            """simple docstring"""







            return self.embeddings.word_embeddings




       def 					a_					(					self      : Dict	,    A__      : str					):


            """simple docstring"""







            __lowerCamelCase						:       List[Any]				   =				value




       def 					a_					(					self      : Optional[int]	,    A__      : Optional[int]					):


            """simple docstring"""







            for layer, heads in heads_to_prune.items():
                 self.encoder.layer[layer].attention.prune_heads(A__					)




       @add_start_docstrings_to_model_forward(A__					)
       def 					a_					(					self      : Optional[int]	,    A__      : int=None	,    A__      : List[str]=None	,    A__      : Optional[int]=None	,    A__      : List[str]=None	,    A__      : List[Any]=None	,    A__      : Dict=None	,    A__      : Union[str, Any]=None	,    A__      : str=None	,    ):


            """simple docstring"""







            if input_ids is not None and inputs_embeds is not None:
                 raise ValueError("""You cannot specify both input_ids and inputs_embeds at the same time"""					)
            elif input_ids is not None:
                 __lowerCamelCase						:       List[str]				   =				input_ids.size()
            elif inputs_embeds is not None:
                 __lowerCamelCase						:       Optional[Any]				   =				inputs_embeds.size()[:-1]
            else:
                 raise ValueError("""You have to specify either input_ids or inputs_embeds"""					)

            __lowerCamelCase						:       List[Any]				   =				input_ids.device if input_ids is not None else inputs_embeds.device

            if attention_mask is None:
                 __lowerCamelCase						:       Optional[Any]				   =				torch.ones(A__	,    device=A__					)
            if encoder_attention_mask is None:
                 __lowerCamelCase						:       Dict				   =				torch.ones(A__	,    device=A__					)
            if token_type_ids is None:
                 __lowerCamelCase						:       Any				   =				torch.zeros(A__	,    dtype=torch.long	,    device=A__					)

            # We can provide a self-attention mask of dimensions [batch_size, from_seq_length, to_seq_length]
            # ourselves in which case we just need to make it broadcastable to all heads.
            __lowerCamelCase						:       torch.Tensor				   =				self.get_extended_attention_mask(A__	,    A__	,    A__					)

            # If a 2D ou 3D attention mask is provided for the cross-attention
            # we need to make broadcastable to [batch_size, num_heads, seq_length, seq_length]
            if encoder_attention_mask.dim() == 3:
                 __lowerCamelCase						:       List[Any]				   =				encoder_attention_mask[:, None, :, :]
            if encoder_attention_mask.dim() == 2:
                 __lowerCamelCase						:       Tuple				   =				encoder_attention_mask[:, None, None, :]

            __lowerCamelCase						:       List[str]				   =				encoder_extended_attention_mask.to(
                dtype=next(self.parameters()					).dtype					)  # fp16 compatibility
            __lowerCamelCase						:       Any				   =				(1.0 - encoder_extended_attention_mask) * -1_0000.0

            # Prepare head mask if needed
            # 1.0 in head_mask indicate we keep the head
            # attention_probs has shape bsz x n_heads x N x N
            # input head_mask has shape [num_heads] or [num_hidden_layers x num_heads]
            # and head_mask is converted to shape [num_hidden_layers x batch x num_heads x seq_length x seq_length]
            __lowerCamelCase						:       Dict				   =				self.get_head_mask(A__	,    self.config.num_hidden_layers					)

            __lowerCamelCase						:       Tuple				   =				self.embeddings(
                input_ids=A__	,    position_ids=A__	,    token_type_ids=A__	,    inputs_embeds=A__					)
            __lowerCamelCase						:       Union[str, Any]				   =				self.encoder(
                A__	,    attention_mask=A__	,    head_mask=A__	,    encoder_hidden_states=A__	,    encoder_attention_mask=A__	,    )
            __lowerCamelCase						:       List[str]				   =				encoder_outputs[0]
            __lowerCamelCase						:       Dict				   =				self.pooler(A__					)

            __lowerCamelCase						:       List[Any]				   =				(
                sequence_output,
                pooled_output,
            ) + encoder_outputs[
                1:
            ]  # add hidden_states and attentions if they are here
            return outputs  # sequence_output, pooled_output, (hidden_states), (attentions), highway exits







class 	SCREAMING_SNAKE_CASE	(      lowerCAmelCase_  ):




       def __init__(					self      : Optional[Any]	,    A__      : Optional[Any]	,    A__      : Optional[Any]					):


            """simple docstring"""







            __lowerCamelCase						:       Dict				   =				message
            __lowerCamelCase						:       Any				   =				exit_layer  # start from 1!







class 	SCREAMING_SNAKE_CASE	(      nn.Module  ):




       def __init__(					self      : Any	,    A__      : int					):


            """simple docstring"""







            super().__init__()
            __lowerCamelCase						:       List[Any]				   =				BertPooler(A__					)
            __lowerCamelCase						:       Optional[Any]				   =				nn.Dropout(config.hidden_dropout_prob					)
            __lowerCamelCase						:       Optional[Any]				   =				nn.Linear(config.hidden_size	,    config.num_labels					)




       def 					a_					(					self      : int	,    A__      : str					):


            """simple docstring"""







            __lowerCamelCase						:       Tuple				   =				encoder_outputs[0]
            __lowerCamelCase						:       int				   =				self.pooler(A__					)
            # "return" pooler_output

            # BertModel
            __lowerCamelCase						:       int				   =				(pooler_input, pooler_output) + encoder_outputs[1:]
            # "return" bmodel_output

            # Dropout and classification
            __lowerCamelCase						:       Optional[int]				   =				bmodel_output[1]

            __lowerCamelCase						:       List[str]				   =				self.dropout(A__					)
            __lowerCamelCase						:       int				   =				self.classifier(A__					)

            return logits, pooled_output







@add_start_docstrings(
    'Bert Model (with early exiting - DeeBERT) with a classifier on top,\n    also takes care of multi-layer training. '    ,   lowerCAmelCase_    ,   )
class 	SCREAMING_SNAKE_CASE	(      lowerCAmelCase_  ):




       def __init__(					self      : Dict	,    A__      : Optional[Any]					):


            """simple docstring"""







            super().__init__(A__					)
            __lowerCamelCase						:       int				   =				config.num_labels
            __lowerCamelCase						:       Union[str, Any]				   =				config.num_hidden_layers

            __lowerCamelCase						:       Optional[Any]				   =				DeeBertModel(A__					)
            __lowerCamelCase						:       Optional[int]				   =				nn.Dropout(config.hidden_dropout_prob					)
            __lowerCamelCase						:       int				   =				nn.Linear(config.hidden_size	,    self.config.num_labels					)

            self.init_weights()




       @add_start_docstrings_to_model_forward(A__					)
       def 					a_					(					self      : Any	,    A__      : Optional[int]=None	,    A__      : List[Any]=None	,    A__      : int=None	,    A__      : Any=None	,    A__      : Dict=None	,    A__      : Optional[Any]=None	,    A__      : Union[str, Any]=None	,    A__      : Tuple=-1	,    A__      : List[Any]=False	,    ):


            """simple docstring"""







            __lowerCamelCase						:       List[str]				   =				self.num_layers
            try:
                 __lowerCamelCase						:       Union[str, Any]				   =				self.bert(
                     A__	,    attention_mask=A__	,    token_type_ids=A__	,    position_ids=A__	,    head_mask=A__	,    inputs_embeds=A__	,    )
                 # sequence_output, pooled_output, (hidden_states), (attentions), highway exits

                 __lowerCamelCase						:       int				   =				outputs[1]

                 __lowerCamelCase						:       List[str]				   =				self.dropout(A__					)
                 __lowerCamelCase						:       Optional[Any]				   =				self.classifier(A__					)
                 __lowerCamelCase						:       List[str]				   =				(logits,) + outputs[2:]  # add hidden states and attention if they are here
            except HighwayException as e:
                 __lowerCamelCase						:       Tuple				   =				e.message
                 __lowerCamelCase						:       Dict				   =				e.exit_layer
                 __lowerCamelCase						:       str				   =				outputs[0]

            if not self.training:
                 __lowerCamelCase						:       List[str]				   =				entropy(A__					)
                 __lowerCamelCase						:       str				   =				[]
                 __lowerCamelCase						:       Optional[Any]				   =				[]
            if labels is not None:
                 if self.num_labels == 1:
                      #  We are doing regression
                      __lowerCamelCase						:       Tuple				   =				MSELoss()
                      __lowerCamelCase						:       Union[str, Any]				   =				loss_fct(logits.view(-1					)	,    labels.view(-1					)					)
                 else:
                      __lowerCamelCase						:       Dict				   =				CrossEntropyLoss()
                      __lowerCamelCase						:       List[str]				   =				loss_fct(logits.view(-1	,    self.num_labels					)	,    labels.view(-1					)					)

                 # work with highway exits
                 __lowerCamelCase						:       Tuple				   =				[]
                 for highway_exit in outputs[-1]:
                      __lowerCamelCase						:       List[str]				   =				highway_exit[0]
                      if not self.training:
                           highway_logits_all.append(A__					)
                           highway_entropy.append(highway_exit[2]					)
                      if self.num_labels == 1:
                           #  We are doing regression
                           __lowerCamelCase						:       List[str]				   =				MSELoss()
                           __lowerCamelCase						:       str				   =				loss_fct(highway_logits.view(-1					)	,    labels.view(-1					)					)
                      else:
                           __lowerCamelCase						:       Any				   =				CrossEntropyLoss()
                           __lowerCamelCase						:       str				   =				loss_fct(highway_logits.view(-1	,    self.num_labels					)	,    labels.view(-1					)					)
                      highway_losses.append(A__					)

                 if train_highway:
                      __lowerCamelCase						:       Any				   =				(sum(highway_losses[:-1]					),) + outputs
                      # exclude the final highway, of course
                 else:
                      __lowerCamelCase						:       Tuple				   =				(loss,) + outputs
            if not self.training:
                 __lowerCamelCase						:       Union[str, Any]				   =				outputs + ((original_entropy, highway_entropy), exit_layer)
                 if output_layer >= 0:
                      __lowerCamelCase						:       str				   =				(
                          (outputs[0],) + (highway_logits_all[output_layer],) + outputs[2:]
                      )  # use the highway of the last layer

            return outputs  # (loss), logits, (hidden_states), (attentions), (highway_exits)











'''simple docstring'''

UpperCAmelCase__						:List[Any]          =			256
# Modulus to hash a string
UpperCAmelCase__						:str          =			1_000_003
def     __lowercase  (_lowercase,						_lowercase     )   ->     bool:


     """simple docstring"""
     __lowerCamelCase						:       str				   =				len(_lowercase     )
     __lowerCamelCase						:       List[str]				   =				len(_lowercase     )
     if p_len > t_len:
          return False

     __lowerCamelCase						:       Optional[Any]				   =				0
     __lowerCamelCase						:       Tuple				   =				0
     __lowerCamelCase						:       Dict				   =				1

     # Calculating the hash of pattern and substring of text
     for i in range(_lowercase     ):
          __lowerCamelCase						:       Optional[int]				   =				(ord(pattern[i]     ) + p_hash * alphabet_size) % modulus
          __lowerCamelCase						:       Dict				   =				(ord(text[i]     ) + text_hash * alphabet_size) % modulus
          if i == p_len - 1:
               continue
          __lowerCamelCase						:       Dict				   =				(modulus_power * alphabet_size) % modulus

     for i in range(0,						t_len - p_len + 1     ):
          if text_hash == p_hash and text[i : i + p_len] == pattern:
               return True
          if i == t_len - p_len:
               continue
          # Calculate the https://en.wikipedia.org/wiki/Rolling_hash
          __lowerCamelCase						:       Dict				   =				(
              (text_hash - ord(text[i]     ) * modulus_power) * alphabet_size
              + ord(text[i + p_len]     )
          ) % modulus
     return False
def     __lowercase  ()   ->     None:


     """simple docstring"""
     __lowerCamelCase						:       List[Any]				   =				"""abc1abc12"""
     __lowerCamelCase						:       Optional[Any]				   =				"""alskfjaldsabc1abc1abc12k23adsfabcabc"""
     __lowerCamelCase						:       List[Any]				   =				"""alskfjaldsk23adsfabcabc"""
     assert rabin_karp(_lowercase,						_lowercase     ) and not rabin_karp(_lowercase,						_lowercase     )

     # Test 2)
     __lowerCamelCase						:       Optional[int]				   =				"""ABABX"""
     __lowerCamelCase						:       Dict				   =				"""ABABZABABYABABX"""
     assert rabin_karp(_lowercase,						_lowercase     )

     # Test 3)
     __lowerCamelCase						:       Any				   =				"""AAAB"""
     __lowerCamelCase						:       int				   =				"""ABAAAAAB"""
     assert rabin_karp(_lowercase,						_lowercase     )

     # Test 4)
     __lowerCamelCase						:       Any				   =				"""abcdabcy"""
     __lowerCamelCase						:       Dict				   =				"""abcxabcdabxabcdabcdabcy"""
     assert rabin_karp(_lowercase,						_lowercase     )

     # Test 5)
     __lowerCamelCase						:       str				   =				"""Lü"""
     __lowerCamelCase						:       str				   =				"""Lüsai"""
     assert rabin_karp(_lowercase,						_lowercase     )
     __lowerCamelCase						:       Tuple				   =				"""Lue"""
     assert not rabin_karp(_lowercase,						_lowercase     )
     print("""Success."""     )


if __name__ == "__main__":
   test_rabin_karp()



