An improved algorithm for solving the banded cyclic string-to-string correction problem

摘要

The banded cyclic string-to-string correction (BCSSC) problem is a generalized version of the cyclic string-to-string correction (CSSC) problem, and has some applications in stereo matching and speech recognition. This note presents an improved algorithm for solving the BCSSC problem and the time complexity required ranges from O(nm) to O(nm log b), where n and m are the lengths of the two strings and b is the allowable bandwidth. The result of this paper generalizes the result of Gregor and Thomason (1996) for solving the CSSC problem since the special version of the BCSSC problem can be transformed into the CSSC problem when setting b = m. (C) 1998-Elsevier Science B.V. All rights reserved. References: 14