Guest User

Untitled

a guest
Oct 16th, 2016
65
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def M(X,Y):
  2.         X = "!"+X # place a terminator character to ignore at front of string
  3.         Y = "!"+Y # place a terminator character to ignore at front of string
  4.         m = len(X)-1
  5.         n = len(Y)-1
  6.         T = [[float('inf')]*(len(Y)+1) for i in xrange(len(X)+1)]
  7.  
  8.         for i in range(0,m,1):
  9.                 for j in range(0,n,1):
  10.                         if (i==0 or j==0):
  11.                                 T[i][j]=0
  12.                         else:
  13.                                 if (X[i]!=Y[j]): val = T[i-1][j-1]+1
  14.                                 else: val = T[i-1][j-1]
  15.                                 T[i][j] = min(T[i-1][j]+1,T[i][j-1]+1,val)
  16.         return T[m-1][n-1]
  17.  
  18. X = "ALGOSCS505"
  19. Y = "ALGORITHMS"
  20. print M(X,Y)
RAW Paste Data