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