A Fast On-Line Algorithm for the Longest Common Subsequence Problem with Constant Alphabet
Summary :
This article presents an algorithm that solves an on-line version of the longest common subsequence (LCS) problem for two strings over a constant alphabet in O(d+n) time and O(m+d) space, where m is the length of the shorter string, the whole of which is given to the algorithm in advance, n is the length of the longer string, which is given as a data stream, and d is the number of dominant matches between the two strings. A new upper bound, O(p(m-q)), of d is also presented, where p is the length of the LCS of the two strings, and q is the length of the LCS of the shorter string and the m-length prefix of the longer string.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E95-A No.1 pp.354-361
- Publication Date
- 2012/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E95.A.354
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yoshifumi SAKAI, "A Fast On-Line Algorithm for the Longest Common Subsequence Problem with Constant Alphabet" in IEICE TRANSACTIONS on Fundamentals,
vol. E95-A, no. 1, pp. 354-361, January 2012, doi: 10.1587/transfun.E95.A.354.
Abstract: This article presents an algorithm that solves an on-line version of the longest common subsequence (LCS) problem for two strings over a constant alphabet in O(d+n) time and O(m+d) space, where m is the length of the shorter string, the whole of which is given to the algorithm in advance, n is the length of the longer string, which is given as a data stream, and d is the number of dominant matches between the two strings. A new upper bound, O(p(m-q)), of d is also presented, where p is the length of the LCS of the two strings, and q is the length of the LCS of the shorter string and the m-length prefix of the longer string.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E95.A.354/_p
Copy
@ARTICLE{e95-a_1_354,
author={Yoshifumi SAKAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Fast On-Line Algorithm for the Longest Common Subsequence Problem with Constant Alphabet},
year={2012},
volume={E95-A},
number={1},
pages={354-361},
abstract={This article presents an algorithm that solves an on-line version of the longest common subsequence (LCS) problem for two strings over a constant alphabet in O(d+n) time and O(m+d) space, where m is the length of the shorter string, the whole of which is given to the algorithm in advance, n is the length of the longer string, which is given as a data stream, and d is the number of dominant matches between the two strings. A new upper bound, O(p(m-q)), of d is also presented, where p is the length of the LCS of the two strings, and q is the length of the LCS of the shorter string and the m-length prefix of the longer string.},
keywords={},
doi={10.1587/transfun.E95.A.354},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - A Fast On-Line Algorithm for the Longest Common Subsequence Problem with Constant Alphabet
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 354
EP - 361
AU - Yoshifumi SAKAI
PY - 2012
DO - 10.1587/transfun.E95.A.354
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E95-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2012
AB - This article presents an algorithm that solves an on-line version of the longest common subsequence (LCS) problem for two strings over a constant alphabet in O(d+n) time and O(m+d) space, where m is the length of the shorter string, the whole of which is given to the algorithm in advance, n is the length of the longer string, which is given as a data stream, and d is the number of dominant matches between the two strings. A new upper bound, O(p(m-q)), of d is also presented, where p is the length of the LCS of the two strings, and q is the length of the LCS of the shorter string and the m-length prefix of the longer string.
ER -
English
