I couldn't get your regex to work for me, so I was thinking that, while regexen are usually fast and compact, using a regex here is actually slowing things down dramatically.

I would use Algorithm::Diff::XS here. For example,

#!/usr/bin/perl -l

use strict;
use warnings;
use Algorithm::Diff::XS qw(LCS);

my(@a) = split (//, q[a c s f 'pl' j k s], 0);
my(@b)= split(//, q[m e f z  x  s  f 'pl'], 0);
print  LCS( \@a,\@b );
[download]

prints out s f 'pl', but it's a lot less work than using a regexp. It can be modified to fit into your decreasing order scheme.