| Mussa | 5a04c91 | 2015-07-21 20:10:00 -0700 | [diff] [blame] | 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] |