





'''simple docstring'''

lowercase__						:      int	=    2_56
# Modulus to hash a string
lowercase__						:      Any	=    1_00_00_03







def  a__    (    lowercase :					str, lowercase :					str				)		->		Any:





     """simple docstring"""

     _UpperCamelCase       =	len(lowerCamelCase_				)
     _UpperCamelCase       =	len(lowerCamelCase_				)
     if p_len > t_len:
          return False

     _UpperCamelCase       =	0
     _UpperCamelCase       =	0
     _UpperCamelCase       =	1

     # Calculating the hash of pattern and substring of text
     for i in range(lowerCamelCase_				):
          _UpperCamelCase       =	(ord(pattern[i]				) + p_hash * alphabet_size) % modulus
          _UpperCamelCase       =	(ord(text[i]				) + text_hash * alphabet_size) % modulus
          if i == p_len - 1:
               continue
          _UpperCamelCase       =	(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
          _UpperCamelCase       =	(
              (text_hash - ord(text[i]				) * modulus_power) * alphabet_size
              + ord(text[i + p_len]				)
          ) % modulus
     return False







def  a__    (    )		->		Optional[int]:





     """simple docstring"""

     _UpperCamelCase       =	"""abc1abc12"""
     _UpperCamelCase       =	"""alskfjaldsabc1abc1abc12k23adsfabcabc"""
     _UpperCamelCase       =	"""alskfjaldsk23adsfabcabc"""
     assert rabin_karp(lowerCamelCase_, lowerCamelCase_				) and not rabin_karp(lowerCamelCase_, lowerCamelCase_				)

     # Test 2)
     _UpperCamelCase       =	"""ABABX"""
     _UpperCamelCase       =	"""ABABZABABYABABX"""
     assert rabin_karp(lowerCamelCase_, lowerCamelCase_				)

     # Test 3)
     _UpperCamelCase       =	"""AAAB"""
     _UpperCamelCase       =	"""ABAAAAAB"""
     assert rabin_karp(lowerCamelCase_, lowerCamelCase_				)

     # Test 4)
     _UpperCamelCase       =	"""abcdabcy"""
     _UpperCamelCase       =	"""abcxabcdabxabcdabcdabcy"""
     assert rabin_karp(lowerCamelCase_, lowerCamelCase_				)

     # Test 5)
     _UpperCamelCase       =	"""Lü"""
     _UpperCamelCase       =	"""Lüsai"""
     assert rabin_karp(lowerCamelCase_, lowerCamelCase_				)
     _UpperCamelCase       =	"""Lue"""
     assert not rabin_karp(lowerCamelCase_, lowerCamelCase_				)
     print('''Success.'''				)


if __name__ == "__main__":
  test_rabin_karp()










'''simple docstring'''

import unittest

from transformers.utils.backbone_utils import (
    BackboneMixin,
    get_aligned_output_features_output_indices,
    verify_out_features_out_indices,
)
class     __lowerCAmelCase					(   unittest.TestCase			):






       """simple docstring"""





       def snake_case__						(							self       :		Optional[Any]					)   ->					List[str]:

            '''simple docstring'''




            _UpperCamelCase       =	['''a''', '''b''', '''c''']

            # Defaults to last layer if both are None
            _UpperCamelCase   ,    _UpperCamelCase       =	get_aligned_output_features_output_indices(lowerCAmelCase__	,			lowerCAmelCase__	,			lowerCAmelCase__					)
            self.assertEqual(lowerCAmelCase__	,			['''c''']					)
            self.assertEqual(lowerCAmelCase__	,			[2]					)

            # Out indices set to match out features
            _UpperCamelCase   ,    _UpperCamelCase       =	get_aligned_output_features_output_indices(['''a''', '''c''']	,			lowerCAmelCase__	,			lowerCAmelCase__					)
            self.assertEqual(lowerCAmelCase__	,			['''a''', '''c''']					)
            self.assertEqual(lowerCAmelCase__	,			[0, 2]					)

            # Out features set to match out indices
            _UpperCamelCase   ,    _UpperCamelCase       =	get_aligned_output_features_output_indices(lowerCAmelCase__	,			[0, 2]	,			lowerCAmelCase__					)
            self.assertEqual(lowerCAmelCase__	,			['''a''', '''c''']					)
            self.assertEqual(lowerCAmelCase__	,			[0, 2]					)

            # Out features selected from negative indices
            _UpperCamelCase   ,    _UpperCamelCase       =	get_aligned_output_features_output_indices(lowerCAmelCase__	,			[-3, -1]	,			lowerCAmelCase__					)
            self.assertEqual(lowerCAmelCase__	,			['''a''', '''c''']					)
            self.assertEqual(lowerCAmelCase__	,			[-3, -1]					)





       def snake_case__						(							self       :		Any					)   ->					Union[str, Any]:

            '''simple docstring'''




            with self.assertRaises(lowerCAmelCase__					):
                 verify_out_features_out_indices(['''a''', '''b''']	,			(0, 1)	,			lowerCAmelCase__					)

            # Out features must be a list
            with self.assertRaises(lowerCAmelCase__					):
                 verify_out_features_out_indices(('''a''', '''b''')	,			(0, 1)	,			['''a''', '''b''']					)

            # Out features must be a subset of stage names
            with self.assertRaises(lowerCAmelCase__					):
                 verify_out_features_out_indices(['''a''', '''b''']	,			(0, 1)	,			['''a''']					)

            # Out indices must be a list or tuple
            with self.assertRaises(lowerCAmelCase__					):
                 verify_out_features_out_indices(lowerCAmelCase__	,			0	,			['''a''', '''b''']					)

            # Out indices must be a subset of stage names
            with self.assertRaises(lowerCAmelCase__					):
                 verify_out_features_out_indices(lowerCAmelCase__	,			(0, 1)	,			['''a''']					)

            # Out features and out indices must be the same length
            with self.assertRaises(lowerCAmelCase__					):
                 verify_out_features_out_indices(['''a''', '''b''']	,			(0,)	,			['''a''', '''b''', '''c''']					)

            # Out features should match out indices
            with self.assertRaises(lowerCAmelCase__					):
                 verify_out_features_out_indices(['''a''', '''b''']	,			(0, 2)	,			['''a''', '''b''', '''c''']					)

            # Out features and out indices should be in order
            with self.assertRaises(lowerCAmelCase__					):
                 verify_out_features_out_indices(['''b''', '''a''']	,			(0, 1)	,			['''a''', '''b''']					)

            # Check passes with valid inputs
            verify_out_features_out_indices(['''a''', '''b''', '''d''']	,			(0, 1, -1)	,			['''a''', '''b''', '''c''', '''d''']					)







       def snake_case__						(							self       :		Any					)   ->					str:

            '''simple docstring'''




            _UpperCamelCase       =	BackboneMixin()

            _UpperCamelCase       =	['''a''', '''b''', '''c''']
            _UpperCamelCase       =	['''a''', '''c''']
            _UpperCamelCase       =	[0, 2]

            # Check that the output features and indices are set correctly
            self.assertEqual(backbone.out_features	,			['''a''', '''c''']					)
            self.assertEqual(backbone.out_indices	,			[0, 2]					)

            # Check out features and indices are updated correctly
            _UpperCamelCase       =	['''a''', '''b''']
            self.assertEqual(backbone.out_features	,			['''a''', '''b''']					)
            self.assertEqual(backbone.out_indices	,			[0, 1]					)

            _UpperCamelCase       =	[-3, -1]
            self.assertEqual(backbone.out_features	,			['''a''', '''c''']					)
            self.assertEqual(backbone.out_indices	,			[-3, -1]					)



