1 # Copyright 2015 The Chromium OS Authors. All rights reserved. 2 # Use of this source code is governed by a BSD-style license that can be 3 # found in the LICENSE file. 4 5 # Utilities for operations on sequences / lists 6 7 8 def lcs_length(x, y): 9 """ 10 Computes the length of a Longest Common Subsequence (LCS) of x and y. 11 12 Algorithm adapted from "Introduction to Algorithms" - CLRS. 13 14 @param x: list, one sequence 15 @param y: list, the other sequence 16 17 """ 18 m = len(x) 19 n = len(y) 20 c = dict() # Use dictionary as a 2D array, keys are tuples 21 22 for i in range(m + 1): 23 c[i, 0] = 0 24 25 for j in range(n + 1): 26 c[0, j] = 0 27 28 for i in range(1, m + 1): 29 for j in range(1, n + 1): 30 if x[i - 1] == y[j - 1]: 31 c[i, j] = c[i - 1, j - 1] + 1 32 else: 33 c[i, j] = max(c[i - 1, j], c[i, j - 1]) 34 35 return c[m, n]
