sequence_utils.py revision 5a04c913266fd9aa50a6393e2c3c059b19e5168d 
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
8def 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]