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