Remark on Hsu-Du New Algorithm for the LCS Problem
Alberto Apostolico · Purdue e-Pubs (Purdue University System) · 1985
One of the time bounds claimed by Hsu and Du for the modification of Hirschberg's strategy set up by them is not correct.This is of some consequence, notably, it voids the claim, made else~ where in the same paper, that the proposed algorithm performs better than the Hunt-Szymanski's strategy in cases of sparse matches.In fact it is pointed out here tbat just the opposite is true.In addition, there are other cases in which the new algorithm fails to achieve the superior performance that the authors cairn, namely, all cases where the number of matches is large compared to the length of the shorter input string.