The Library
Semi-local string comparison : algorithmic techniques and applications
Tools
Tiskin, Alexander (2008) Semi-local string comparison : algorithmic techniques and applications. Mathematics in Computer Science, Volume 1 (Number 4). pp. 571-603. doi:10.1007/s11786-007-0033-3 ISSN 1661-8270.
PDF
fulltext.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (410Kb) |
Official URL: http://dx.doi.org/10.1007/s11786-007-0033-3
Abstract
Given two strings, the longest common subsequence (LCS) problem consists in computing the length of the longest string that is a subsequence of both input strings. Its generalisation, the all semi-local LCS problem, requires computing the LCS length for each string against all substrings of the other string, and for all prefixes of each string against all suffixes of the other string. We survey a number of algorithmic techniques related to the all semi-local LCS problem. We then present a number of algorithmic applications of these techniques, both existing and new. In particular, we obtain a new all semilocal
LCS algorithm, with asymptotic running time matching (in the case of an unbounded alphabet) the fastest known global LCS algorithm by Masek and Paterson. We conclude that semi-local string comparison turns out to be a useful algorithmic plug-in, which unifies, and often improves on, a number of previous approaches to various substring- and subsequence-related problems.
Item Type: | Journal Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||
Journal or Publication Title: | Mathematics in Computer Science | ||||||||||
Publisher: | Birkhaeuser Verlag AG | ||||||||||
ISSN: | 1661-8270 | ||||||||||
Official Date: | 1 June 2008 | ||||||||||
Dates: |
|
||||||||||
Volume: | Volume 1 | ||||||||||
Number: | Number 4 | ||||||||||
Page Range: | pp. 571-603 | ||||||||||
DOI: | 10.1007/s11786-007-0033-3 | ||||||||||
Status: | Peer Reviewed | ||||||||||
Publication Status: | Published | ||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||
Date of first compliant deposit: | 21 December 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |