[Maxima] pattern matching

Xiang Liu hsiang.liu at gmail.com
Tue Mar 3 23:58:26 CST 2009

```I have no idea on Maxima's approach. But your problem is a typical longest
common sequence in Algorithm.

We write A=A[1:n], B=B[1:m]. Now,

if A[n]=B[n] then
result=common(A[1,n-1],B[1,n-1]).append(A[n]);
else
result=longerOne( common(A[1,n-1], B[1,n]), common(A[1,n], B[1,n-1]) );

The pseudo code above is just a skeleton.

On Wed, Mar 4, 2009 at 12:10 AM, Paulo Grahl <pgrahl at gmail.com> wrote:

> Dear list members:
>
> I'm facing the following problem:
> given a two lists, for example, [a,b,c,x,a] and [z,a,a,b]
> I'm interested in finding the largest sequence of symbols that match
> both lists, considering lists as circular, i.e.,
> [z,a,a,b]=[a,a,b,z]=[a,b,z,a]=[b,z,a,a].
> In the above example, the sequence "a,b" appears in both lists, but I
> would be interested in finding the sequence "a,a,b" which is the
> longest one to appear in both lists (considering the lists as
> circular).
>
> Any idea on how to find such common patterns ?
> Thanks.
> Paulo
>
>
> Paulo Gustavo Grahl, CFA
> ------------------------------------------
> pgrahl at gmail.com
> pgrahl at fgvmail.br
> +55(21) 8809-9254