'''simple docstring'''



class       __SCREAMING_SNAKE_CASE	:



     '''simple docstring'''






     def __init__(					self	):
       _snake_case     		=				""
       _snake_case     		=				""
       _snake_case     		=				[]

     def 	UpperCamelCase(					self						,   lowerCamelCase						,   lowerCamelCase	):
       if m == -1:
         return n + 1
       elif n == -1:
         return m + 1
       elif self.dp[m][n] > -1:
         return self.dp[m][n]
       else:
         if self.worda[m] == self.worda[n]:
           _snake_case     		=				self.__min_dist_top_down_dp(m - 1						,   n - 1	)
         else:
           _snake_case     		=				self.__min_dist_top_down_dp(lowerCamelCase						,   n - 1	)
           _snake_case     		=				self.__min_dist_top_down_dp(m - 1						,   lowerCamelCase	)
           _snake_case     		=				self.__min_dist_top_down_dp(m - 1						,   n - 1	)
           _snake_case     		=				1 + min(lowerCamelCase						,   lowerCamelCase						,   lowerCamelCase	)

         return self.dp[m][n]

     def 	UpperCamelCase(					self						,   lowerCamelCase						,   lowerCamelCase	):
       _snake_case     		=				worda
       _snake_case     		=				worda
       _snake_case     		=				[[-1 for _ in range(len(lowerCamelCase	)	)] for _ in range(len(lowerCamelCase	)	)]

       return self.__min_dist_top_down_dp(len(lowerCamelCase	) - 1						,   len(lowerCamelCase	) - 1	)






     def 	UpperCamelCase(					self						,   lowerCamelCase						,   lowerCamelCase	):
       _snake_case     		=				worda
       _snake_case     		=				worda
       _snake_case     		=				len(lowerCamelCase	)
       _snake_case     		=				len(lowerCamelCase	)
       _snake_case     		=				[[0 for _ in range(n + 1	)] for _ in range(m + 1	)]

       for i in range(m + 1	):
         for j in range(n + 1	):
           if i == 0:  # first string is empty
             _snake_case     		=				j
           elif j == 0:  # second string is empty
             _snake_case     		=				i
           elif worda[i - 1] == worda[j - 1]:  # last characters are equal
             _snake_case     		=				self.dp[i - 1][j - 1]
           else:
             _snake_case     		=				self.dp[i][j - 1]
             _snake_case     		=				self.dp[i - 1][j]
             _snake_case     		=				self.dp[i - 1][j - 1]
             _snake_case     		=				1 + min(lowerCamelCase						,   lowerCamelCase						,   lowerCamelCase	)
       return self.dp[m][n]


if __name__ == "__main__":
 __magic_name__   :						List[Any]    =			EditDistance()

 print("""****************** Testing Edit Distance DP Algorithm ******************""")
 print()

 __magic_name__   :						Optional[Any]    =			input("""Enter the first string: """).strip()
 __magic_name__   :						List[str]    =			input("""Enter the second string: """).strip()

 print()
 print(F'The minimum edit distance is: {solver.min_dist_top_down(Sa, Sa)}')
 print(F'The minimum edit distance is: {solver.min_dist_bottom_up(Sa, Sa)}')
 print()
 print("""*************** End of Testing Edit Distance DP Algorithm ***************""")









'''simple docstring'''



def 				snake_case_      (		SCREAMING_SNAKE_CASE__       ):







  '''simple docstring'''



  _snake_case     		=				[0 for i in range(len(SCREAMING_SNAKE_CASE__       )       )]

  # initialize interval's left pointer and right pointer
  _snake_case		,		_snake_case     		=				0, 0

  for i in range(1					,	len(SCREAMING_SNAKE_CASE__       )       ):
    # case when current index is inside the interval
    if i <= right_pointer:
      _snake_case     		=				min(right_pointer - i + 1					,	z_result[i - left_pointer]       )
      _snake_case     		=				min_edge

    while go_next(SCREAMING_SNAKE_CASE__					,	SCREAMING_SNAKE_CASE__					,	SCREAMING_SNAKE_CASE__       ):
      z_result[i] += 1

    # if new index's result gives us more right interval,
    # we've to update left_pointer and right_pointer
    if i + z_result[i] - 1 > right_pointer:
      _snake_case		,		_snake_case     		=				i, i + z_result[i] - 1

  return z_result




def 				snake_case_      (		SCREAMING_SNAKE_CASE__					,	SCREAMING_SNAKE_CASE__					,	SCREAMING_SNAKE_CASE__       ):







  '''simple docstring'''



  return i + z_result[i] < len(SCREAMING_SNAKE_CASE__       ) and s[z_result[i]] == s[i + z_result[i]]




def 				snake_case_      (		SCREAMING_SNAKE_CASE__					,	SCREAMING_SNAKE_CASE__       ):







  '''simple docstring'''



  _snake_case     		=				0
  # concatenate 'pattern' and 'input_str' and call z_function
  # with concatenated string
  _snake_case     		=				z_function(pattern + input_str       )

  for val in z_result:
    # if value is greater then length of the pattern string
    # that means this index is starting position of substring
    # which is equal to pattern string
    if val >= len(SCREAMING_SNAKE_CASE__       ):
      answer += 1

  return answer


if __name__ == "__main__":
 import doctest

 doctest.testmod()


