




'''simple docstring'''



class 		lowercase_   :


   """simple docstring"""

   def __init__(   self :     Optional[int]   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				""
      _SCREAMING_SNAKE_CASE	=				""
      _SCREAMING_SNAKE_CASE	=				[]



   def 							lowerCAmelCase_      (   self :     Dict  ,				__lowerCamelCase :     int  ,				__lowerCamelCase :     int   ):

      """simple docstring"""
      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]:
            _SCREAMING_SNAKE_CASE	=				self.__min_dist_top_down_dp(m - 1  ,				n - 1   )
         else:
            _SCREAMING_SNAKE_CASE	=				self.__min_dist_top_down_dp(__lowerCamelCase  ,				n - 1   )
            _SCREAMING_SNAKE_CASE	=				self.__min_dist_top_down_dp(m - 1  ,				__lowerCamelCase   )
            _SCREAMING_SNAKE_CASE	=				self.__min_dist_top_down_dp(m - 1  ,				n - 1   )
            _SCREAMING_SNAKE_CASE	=				1 + min(__lowerCamelCase  ,				__lowerCamelCase  ,				__lowerCamelCase   )

         return self.dp[m][n]



   def 							lowerCAmelCase_      (   self :     Dict  ,				__lowerCamelCase :     str  ,				__lowerCamelCase :     str   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				worda
      _SCREAMING_SNAKE_CASE	=				worda
      _SCREAMING_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 							lowerCAmelCase_      (   self :     Tuple  ,				__lowerCamelCase :     str  ,				__lowerCamelCase :     str   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				worda
      _SCREAMING_SNAKE_CASE	=				worda
      _SCREAMING_SNAKE_CASE	=				len(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				len(__lowerCamelCase   )
      _SCREAMING_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
               _SCREAMING_SNAKE_CASE	=				j
            elif j == 0:  # second string is empty
               _SCREAMING_SNAKE_CASE	=				i
            elif worda[i - 1] == worda[j - 1]:  # last characters are equal
               _SCREAMING_SNAKE_CASE	=				self.dp[i - 1][j - 1]
            else:
               _SCREAMING_SNAKE_CASE	=				self.dp[i][j - 1]
               _SCREAMING_SNAKE_CASE	=				self.dp[i - 1][j]
               _SCREAMING_SNAKE_CASE	=				self.dp[i - 1][j - 1]
               _SCREAMING_SNAKE_CASE	=				1 + min(__lowerCamelCase  ,				__lowerCamelCase  ,				__lowerCamelCase   )
      return self.dp[m][n]


if __name__ == "__main__":
 lowerCamelCase_			=						EditDistance()

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

 lowerCamelCase_			=						input('Enter the first string: ').strip()
 lowerCamelCase_			=						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'''



lowerCamelCase_			=						'Tobias Carryer'

from time import time







class 		lowercase_   :


   """simple docstring"""

   def __init__(   self :     Tuple  ,				__lowerCamelCase :     int  ,				__lowerCamelCase :     List[Any]  ,				__lowerCamelCase :     Optional[int]  ,				__lowerCamelCase :     Dict=int(time()   )   ):  # noqa: B008

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				multiplier
      _SCREAMING_SNAKE_CASE	=				increment
      _SCREAMING_SNAKE_CASE	=				modulo
      _SCREAMING_SNAKE_CASE	=				seed



   def 							lowerCAmelCase_      (   self :     List[str]   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				(self.multiplier * self.seed + self.increment) % self.modulo
      return self.seed


if __name__ == "__main__":
 # Show the LCG in action.
 lowerCamelCase_			=						LinearCongruentialGenerator(1_66_45_25, 10_13_90_42_23, 2 << 31)
 while True:
  print(lcg.next_number())

