class     _A   :






  def __init__(self   ,				SCREAMING_SNAKE_CASE_	)		->      None:





       '''simple docstring'''





       UpperCamelCase__										=      size
       UpperCamelCase__										=      [0] * size
       UpperCamelCase__										=      [0] * size






  @staticmethod
  def 		_a					(SCREAMING_SNAKE_CASE_	)		->      int:





       '''simple docstring'''





       return index | (index + 1)






  @staticmethod
  def 		_a					(SCREAMING_SNAKE_CASE_	)		->      int:





       '''simple docstring'''





       return (index & (index + 1)) - 1






  def 		_a					(self   ,				SCREAMING_SNAKE_CASE_   ,				SCREAMING_SNAKE_CASE_	)		->      None:





       '''simple docstring'''





       UpperCamelCase__										=      value
       while index < self.size:
            UpperCamelCase__										=      self.get_prev(SCREAMING_SNAKE_CASE_	) + 1
            if current_left_border == index:
                 UpperCamelCase__										=      value
            else:
                 UpperCamelCase__										=      max(SCREAMING_SNAKE_CASE_   ,				SCREAMING_SNAKE_CASE_   ,				SCREAMING_SNAKE_CASE_	)
            UpperCamelCase__										=      self.get_next(SCREAMING_SNAKE_CASE_	)






  def 		_a					(self   ,				SCREAMING_SNAKE_CASE_   ,				SCREAMING_SNAKE_CASE_	)		->      int:





       '''simple docstring'''





       right -= 1  # Because of right is exclusive
       UpperCamelCase__										=      0
       while left <= right:
            UpperCamelCase__										=      self.get_prev(SCREAMING_SNAKE_CASE_	)
            if left <= current_left:
                 UpperCamelCase__										=      max(SCREAMING_SNAKE_CASE_   ,				self.tree[right]	)
                 UpperCamelCase__										=      current_left
            else:
                 UpperCamelCase__										=      max(SCREAMING_SNAKE_CASE_   ,				self.arr[right]	)
                 right -= 1
       return result


if __name__ == "__main__":
     import doctest

     doctest.testmod()




from __future__ import annotations







def  __UpperCamelCase    (						A ,							A							):
     UpperCamelCase__										=      get_failure_array(A							)

     # 2) Step through text searching for pattern
     UpperCamelCase__						,       UpperCamelCase__										=      0, 0  # index into text, pattern
     while i < len(A							):
          if pattern[j] == text[i]:
               if j == (len(A							) - 1):
                    return True
               j += 1

          # if this is a prefix in our pattern
          # just go back far enough to continue
          elif j > 0:
               UpperCamelCase__										=      failure[j - 1]
               continue
          i += 1
     return False







def  __UpperCamelCase    (						A							):
     UpperCamelCase__										=      [0]
     UpperCamelCase__										=      0
     UpperCamelCase__										=      1
     while j < len(A							):
          if pattern[i] == pattern[j]:
               i += 1
          elif i > 0:
               UpperCamelCase__										=      failure[i - 1]
               continue
          j += 1
          failure.append(A							)
     return failure


if __name__ == "__main__":
     # Test 1)
     __magic_name__								='''abc1abc12'''
     __magic_name__								='''alskfjaldsabc1abc1abc12k23adsfabcabc'''
     __magic_name__								='''alskfjaldsk23adsfabcabc'''
     assert kmp(pattern, texta) and not kmp(pattern, texta)

     # Test 2)
     __magic_name__								='''ABABX'''
     __magic_name__								='''ABABZABABYABABX'''
     assert kmp(pattern, text)

     # Test 3)
     __magic_name__								='''AAAB'''
     __magic_name__								='''ABAAAAAB'''
     assert kmp(pattern, text)

     # Test 4)
     __magic_name__								='''abcdabcy'''
     __magic_name__								='''abcxabcdabxabcdabcdabcy'''
     assert kmp(pattern, text)

     # Test 5)
     __magic_name__								='''aabaabaaa'''
     assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]



