THE LONGEST COMMON SUBSEQUENCE PROBLEM REVISITED

This paper fe-examines. in a unified framework, me problem of finding a longest------commoIr"StIbsequence-CJ:;eS)-oftWo--strings;-anct-proposes--simple-and-generally------------faster implementations for most known approaches. Let l be the length of an LCS between two strings of length m and n~. respectively, and let s be lhe alphabet size. The first revised strategy follows the paradigm of a previous 0 (in) time algoritlun by Hirschberg. The new version can be implemented in time O(fm-min{logs,logmJog(2nlm)}), which is profitable when the inpm strings differ considerably in size (a looser bound for both versions is 0 (mn ». A natural offspring of this algorilhrn is also presented which uses only linear space and has the same time bound. except for an additive term O(mlogm). \vl1ile most exist-ing algorithms use li.1J.ear space in order to compute only l, the only previously known algorimm computing an LCS in linear space required never less than time 8(nm). AnoIher algorirh.m. presemed here improves on the Hunt·Szymanski algoriu.'un. This latter takes time o«r+n) logn), where r$mn is the total number of marches berween the cwo input silings. Such a performance is quir