Квейд,

Если времени не жалко, придумать можно много чего. Скажем, взять функцию нахождения общей подпоследовательности для хвостов последовательностей, где воспользоваться тем правилом, что либо общая подпоследовательность содержит первый элемент первого хвоста a ₁ , и тогда нас не интересуют элементы второго хвоста до первого b _i равного a ₁ , либо нас не интересует a ₁ . Если во второй последовательности много разных элементов, места должно жраться существенно меньше. Но это всё равно O(A*B)
Теоретически, можно ограничиться памятью порядка O(A+B) - создать вектор пар с возможностью одного из элементов пары быть пустым и перебирать все возможные размещения "разреженной" последовательности A "над" разреженной последовательностью B. Но это будет реально долго.

Квейд,

Могу подкинуть ещё одно соображение.
В множестве максимальных подпоследовательностей существует такая C , что для любых c _t , c _t+1 , c _t+2 , соответствующих a _i , a _j , a _k ; b _l , b _m , b _n , между b _l и b _n не существует элемента, равного какому-либо из находящихся между a _i и a _j .
Таким образом, если для очередного кандидата последний найденный элемент соответствует паре (a _i , b _l ), то следующий элемент либо a _i+1 в паре с первым равным ему после b _l b _x , либо a _i+2 , но уже при условии, что соответствующий ему b _y предшествует b _x либо a _i+3 , но если соответствующий ему b _z предшествует b _y и b _x и т.д. При сильно похожих последовательностях, может получиться быстро.

Но вообще, уже давали ссылку на универсальный алгоритм, жрущий мало памяти.