TABLE OF CONTENTS Suppose that we have two time series A =( a 1, a 2, , a n)and B = ( b 1, b 2, , b m). For A let Head( A) =( a 1, a 2, , a n ?1). Similarly, for B.
The LCSS between A and B is defined as follows:
The above definition is recursive and would require exponential time to compute. However, there is a better solution that can be offered in O ( m* n) time, using dynamic programming.
The LCSS problem can easily be solved in quadratic time and space. The basic idea behind this solution lies in the fact that the problem of the sequence matching can be dissected in smaller problems, which can be combined after they are solved optimally. So, what we have to do is, solve a smaller instance of the problem (with fewer points) and then continue by adding new points to our sequence and modify accordingly the LCSS.
Now the solution can be found by solving the following equation using dynamic programming (Figure 4):
