




'''simple docstring'''





UpperCamelCase_						:      Optional[Any]       =						256
# Modulus to hash a string
UpperCamelCase_						:      List[str]       =						1000003





def      __a     (       _UpperCamelCase:   str ,						_UpperCamelCase:   str   )						->			bool:

					"""simple docstring"""




					_snake_case							=				len(lowerCAmelCase__   )
					_snake_case							=				len(lowerCAmelCase__   )
					if p_len > t_len:
										return False

					_snake_case							=				0
					_snake_case							=				0
					_snake_case							=				1

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





def      __a     (       )						->			None:

					"""simple docstring"""




					_snake_case							=				"abc1abc12"
					_snake_case							=				"alskfjaldsabc1abc1abc12k23adsfabcabc"
					_snake_case							=				"alskfjaldsk23adsfabcabc"
					assert rabin_karp(lowerCAmelCase__ ,						lowerCAmelCase__   ) and not rabin_karp(lowerCAmelCase__ ,						lowerCAmelCase__   )

					# Test 2)
					_snake_case							=				"ABABX"
					_snake_case							=				"ABABZABABYABABX"
					assert rabin_karp(lowerCAmelCase__ ,						lowerCAmelCase__   )

					# Test 3)
					_snake_case							=				"AAAB"
					_snake_case							=				"ABAAAAAB"
					assert rabin_karp(lowerCAmelCase__ ,						lowerCAmelCase__   )

					# Test 4)
					_snake_case							=				"abcdabcy"
					_snake_case							=				"abcxabcdabxabcdabcdabcy"
					assert rabin_karp(lowerCAmelCase__ ,						lowerCAmelCase__   )

					# Test 5)
					_snake_case							=				"Lü"
					_snake_case							=				"Lüsai"
					assert rabin_karp(lowerCAmelCase__ ,						lowerCAmelCase__   )
					_snake_case							=				"Lue"
					assert not rabin_karp(lowerCAmelCase__ ,						lowerCAmelCase__   )
					print("Success."   )


if __name__ == "__main__":
			test_rabin_karp()








'''simple docstring'''





from __future__ import annotations

from collections import namedtuple
from dataclasses import dataclass

@dataclass
class        _a    :
     SCREAMING_SNAKE_CASE_							:   int
     SCREAMING_SNAKE_CASE_							:   TreeNode | None       =						None
     SCREAMING_SNAKE_CASE_							:   TreeNode | None       =						None







UpperCamelCase_						:      Any       =						namedtuple('''CoinsDistribResult''', '''moves excess''')





def      __a     (       _UpperCamelCase:   TreeNode | None   )						->			int:

     """simple docstring"""




     if root is None:
          return 0

     # Validation
     def count_nodes(_UpperCamelCase:   TreeNode | None   ) -> int:
          if node is None:
               return 0

          return count_nodes(node.left   ) + count_nodes(node.right   ) + 1

     def count_coins(_UpperCamelCase:   TreeNode | None   ) -> int:
          if node is None:
               return 0

          return count_coins(node.left   ) + count_coins(node.right   ) + node.data

     if count_nodes(_UpperCamelCase   ) != count_coins(_UpperCamelCase   ):
          raise ValueError("The nodes number should be same as the number of coins"   )

     # Main calculation
     def get_distrib(_UpperCamelCase:   TreeNode | None   ) -> CoinsDistribResult:

          if node is None:
               return CoinsDistribResult(0 ,						1   )

          _snake_case							, _snake_case							=				get_distrib(node.left   )
          _snake_case							, _snake_case							=				get_distrib(node.right   )

          _snake_case							=				1 - left_distrib_excess
          _snake_case							=				1 - right_distrib_excess

          _snake_case							=				(
              left_distrib_moves
              + right_distrib_moves
              + abs(_UpperCamelCase   )
              + abs(_UpperCamelCase   )
          )
          _snake_case							=				node.data - coins_to_left - coins_to_right

          return CoinsDistribResult(_UpperCamelCase ,						_UpperCamelCase   )

     return get_distrib(_UpperCamelCase   )[0]


if __name__ == "__main__":
   import doctest

   doctest.testmod()


