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 ( m n ) 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 ( m n / log ⁡ n ) , O ( m n / w ) , O ( n s + min ⁡ ( p ( n − p ) , p m ) ) , O ( n log ⁡ s + d log ⁡ log ⁡ min ⁡ ( d , m n / d ) ) , O ( n s + min ⁡ ( d s , p m ) ) , and O ( n s + s ! 2 s + d log ⁡ s ) . In this work, we present an O ( n ( s + log ⁎ ⁡ n ) + min ⁡ ( d log ⁡ s , p m ) ) algorithm when s ∈ O ( w ) , and also an O ( n ( s + log ⁎ ⁡ n ) + d ) algorithm when s ≤ w which uses bitwise instructions that became recently available in modern processors. • The length of the longest common subsequence serves as a string similarity measure. • The number of dominant matches between the strings is usually small. • Algorithms that are sensitive to the number of dominant matches have been devised. • For small alphabets of variable length, it is possible to quickly find the matches. • This paper improves Chin and Poon's algorithm by exploiting bit parallelism.