



A     :  Optional[Any]					     =       2_56
# Modulus to hash a string
A     :  Tuple					     =       1_00_00_03


def      a__ (		__UpperCamelCase     ,      __UpperCamelCase				):
      SCREAMING_SNAKE_CASE_          =  len(__UpperCamelCase				)
      SCREAMING_SNAKE_CASE_          =  len(__UpperCamelCase				)
      if p_len > t_len:
            return False

      SCREAMING_SNAKE_CASE_          =  0
      SCREAMING_SNAKE_CASE_          =  0
      SCREAMING_SNAKE_CASE_          =  1

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


def      a__ (		):
      SCREAMING_SNAKE_CASE_          =  "abc1abc12"
      SCREAMING_SNAKE_CASE_          =  "alskfjaldsabc1abc1abc12k23adsfabcabc"
      SCREAMING_SNAKE_CASE_          =  "alskfjaldsk23adsfabcabc"
      assert rabin_karp(__UpperCamelCase     ,      __UpperCamelCase				) and not rabin_karp(__UpperCamelCase     ,      __UpperCamelCase				)

      # Test 2)
      SCREAMING_SNAKE_CASE_          =  "ABABX"
      SCREAMING_SNAKE_CASE_          =  "ABABZABABYABABX"
      assert rabin_karp(__UpperCamelCase     ,      __UpperCamelCase				)

      # Test 3)
      SCREAMING_SNAKE_CASE_          =  "AAAB"
      SCREAMING_SNAKE_CASE_          =  "ABAAAAAB"
      assert rabin_karp(__UpperCamelCase     ,      __UpperCamelCase				)

      # Test 4)
      SCREAMING_SNAKE_CASE_          =  "abcdabcy"
      SCREAMING_SNAKE_CASE_          =  "abcxabcdabxabcdabcdabcy"
      assert rabin_karp(__UpperCamelCase     ,      __UpperCamelCase				)

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


if __name__ == "__main__":
      test_rabin_karp()



from __future__ import annotations


def      a__ (		__UpperCamelCase				):

      # preprocessing the first row
      for i in range(1     ,      len(matrix[0]				)				):
            matrix[0][i] += matrix[0][i - 1]

      # preprocessing the first column
      for i in range(1     ,      len(__UpperCamelCase				)				):
            matrix[i][0] += matrix[i - 1][0]

      # updating the path cost for current position
      for i in range(1     ,      len(__UpperCamelCase				)				):
            for j in range(1     ,      len(matrix[0]				)				):
                  matrix[i][j] += min(matrix[i - 1][j]     ,      matrix[i][j - 1]				)

      return matrix[-1][-1]


if __name__ == "__main__":
      import doctest

      doctest.testmod()


