A Fast On-Line Algorithm for the Longest Common Subsequence Problem with Constant Alphabet

Yoshifumi SAKAI

doi:10.1587/transfun.E95.A.354

A Fast On-Line Algorithm for the Longest Common Subsequence Problem with Constant Alphabet

Yoshifumi SAKAI

Full Text Views

0

Share
Cite this

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

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://globals.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 -