The longest common subsequence problem for small alphabets in the word RAM model

Given two strings of lengths m and n, with m <= n, the longest common subsequence problem consists of computing a common subsequence of maximum length by deleting symbols from both strings. While the O(mn) algorithm devised in 1974 is optimal in the most general setting, algorithms that depend on parameters other than m and n have been proposed since then. In the word RAM model, let w be the word size, s be the alphabet size, d be the number of dominant symbol matches between the strings, and p be the length of the longest common subsequence. Fast algorithms for this problem have complexities O(mn/ log n), O(mn/w), O(ns + min(p(n - p), pm)), O(n logs + d log log min(d, mn/d)), O(ns+min(ds, pm)), and O(ns+s!2s+d logs). In this work, we present an O(n(s+log & lowast; n)+ min(d logs, pm)) algorithm when s is an element of O(w), and also an O(n(s + log & lowast; n) + d) algorithm when s <= w which uses bitwise instructions that became recently available in modern processors.