# Longest Common Subsequence (LCS)¶

## Standard LCS¶

mlpy.lcs_std(x, y)

Standard Longest Common Subsequence (LCS) algorithm as described in [Cormen01].

The elements of sequences must be coded as integers.

Parameters : x : 1d integer array_like object (N) first sequence y : 1d integer array_like object (M) second sequence length : integer length of the LCS of x and y path : tuple of two 1d numpy array (path_x, path_y) path of the LCS

Example

Reproducing the example in figure 15.6 of [Cormen01], where sequence X = (A, B, C, B, D, A, B) and Y = (B, D, C, A, B, A).

```>>> import mlpy
>>> x = [0,1,2,1,3,0,1] # (A, B, C, B, D, A, B)
>>> y = [1,3,2,0,1,0] # (B, D, C, A, B, A)
>>> length, path = mlpy.lcs_std(x, y)
>>> length
4
>>> path
(array([1, 2, 3, 5]), array([0, 2, 4, 5]))
```
 [Cormen01] (1, 2) H Cormen et al.. Introduction to Algorithms, Second Edition. The MIT Press, 2001.

## LCS for real series¶

mlpy.lcs_real(x, y, eps, delta)

Longest Common Subsequence (LCS) for series composed by real numbers as described in [Vlachos02].

Parameters : x : 1d integer array_like object (N) first sequence y : 1d integer array_like object (M) second sequence eps : float (>=0) matching threshold delta : int (>=0) controls how far in time we can go in order to match a given point from one series to a point in another series length : integer length of the LCS of x and y path : tuple of two 1d numpy array (path_x, path_y) path of the LCS
 [Vlachos02] M Vlachos et al.. Discovering Similar Multidimensional Trajectories. In Proceedings of the 18th international conference on data engineering, 2002

#### Previous topic

Dynamic Time Warping (DTW)

#### Next topic

mlpy.wavelet - Wavelet Transform