Snippets

Camilo Rocha LCS naive

Created by Former user
View revision

File lcs_naive.py Added

  • Ignore whitespace
  • Hide word diff 
+# input: a[0..M) and b[0..N), M>=0 and N>=0
+#
+# output: length of a longest common subsequence of a[0..M) and
+#         b[0..N)
+#
+# exponential (in N and M) naive solution
+
+def lcs_naive(a,b):
+  return lcs_aux(a,b,len(a),len(b))
+
+def lcs_aux(a,b,m,n):
+  ans = None
+  if m==0 or n==0: ans = 0
+  else:
+    if a[m-1]==b[n-1]: ans = 1+lcs_aux(a,b,m-1,n-1)
+    else: ans = max(lcs_aux(a,b,m,n-1),lcs_aux(a,b,m-1,n))
+  return ans
HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.