✦ LIBER ✦

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

✍ Scribed by Chung Kuo-Liang

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 339 KB
Volume: 201
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(97)00280-6

No coin nor oath required. For personal study only.

✦ Synopsis

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(nmlogb),

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.

📜 SIMILAR VOLUMES

A correction to “An optimal algorithm to

A correction to “An optimal algorithm to compute all the covers of a string”

✍ Dennis Moore; W.F. Smyth 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 265 KB

An improved algorithm for computing the

An improved algorithm for computing the edit distance of run-length coded strings

✍ H. Bunke; J. Csirik 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 379 KB

An effective algorithm for string correc

An effective algorithm for string correction using generalized edit distance—II. Computational complexity of the algorithm and some applications

✍ R.L. Kashyap; B.J. Oommen 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 981 KB

An efficient algorithm to solve the smal

An efficient algorithm to solve the small sample size problem for LDA

✍ Wenming Zheng; Li Zhao; Cairong Zou 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 117 KB

Direct algorithms to solve the two-sided

Direct algorithms to solve the two-sided obstacle problem for an M-matrix

✍ J. P. Zeng; Y. J. Jiang 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

An algebraic multigrid wave–ray algorith

An algebraic multigrid wave–ray algorithm to solve eigenvalue problems for the helmholtz operator

✍ Irene Livshits 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract Helmholtz equations with variable coefficients are known to be hard to solve both analytically and numerically. In this paper, we introduce a numerical multigrid solver for one‐dimensional Helmholtz eigenvalue problems with periodic potentials and solutions. The solvers employ wave–ray