File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Fast algorithm for computing longest common subsequences of small alphabet size

TitleFast algorithm for computing longest common subsequences of small alphabet size
Authors
Issue Date1990
Citation
Journal Of Information Processing, 1990, v. 13 n. 4, p. 463-469 How to Cite?
AbstractGiven two strings of lengths m and n≥m on an alphabet of size s, the longest common subsequence (LCS) problem is to determine the longest subsequence that can be obtained by deleting zero or more symbols from either string. The first O(mn) algorithm was given by Hirschberg in 1975. The algorithm was later revised to O(ln), where l is the length of an LCS between the two strings. Another strategy given by Hunt and Szymanski takes O(rlogn) time, where r≤mn is the total number of matches between the two strings. Apostolico and Guerra combined the two approaches and derived an O(mlogn + dlog(mn/d)) algorithm, where d≤r is the number of dominant matches (minimal candidates) between the two strings. Efficient algorithms for two similar strings were devised by Nakatsu et al. [7] and Myers [6] with time complexities of O(n(m-l)) and O(n(n-l)), respectively. This paper presents a new algorithm for this problem, which requires preprocessing that is nearly standard for the LCS problem and has time and space complexity of O(ns + min {ds, lm}) and O(ns + d), respectively. This algorithm is particularly efficient when s (the alphabet size) is small. Different data structures are used to obtain variations of the basic algorithm that require different time and space complexities.
Persistent Identifierhttp://hdl.handle.net/10722/152230
ISSN
2015 SCImago Journal Rankings: 0.178

 

DC FieldValueLanguage
dc.contributor.authorChin, Francis YLen_US
dc.contributor.authorPoon, CKen_US
dc.date.accessioned2012-06-26T06:36:39Z-
dc.date.available2012-06-26T06:36:39Z-
dc.date.issued1990en_US
dc.identifier.citationJournal Of Information Processing, 1990, v. 13 n. 4, p. 463-469en_US
dc.identifier.issn0387-6101en_US
dc.identifier.urihttp://hdl.handle.net/10722/152230-
dc.description.abstractGiven two strings of lengths m and n≥m on an alphabet of size s, the longest common subsequence (LCS) problem is to determine the longest subsequence that can be obtained by deleting zero or more symbols from either string. The first O(mn) algorithm was given by Hirschberg in 1975. The algorithm was later revised to O(ln), where l is the length of an LCS between the two strings. Another strategy given by Hunt and Szymanski takes O(rlogn) time, where r≤mn is the total number of matches between the two strings. Apostolico and Guerra combined the two approaches and derived an O(mlogn + dlog(mn/d)) algorithm, where d≤r is the number of dominant matches (minimal candidates) between the two strings. Efficient algorithms for two similar strings were devised by Nakatsu et al. [7] and Myers [6] with time complexities of O(n(m-l)) and O(n(n-l)), respectively. This paper presents a new algorithm for this problem, which requires preprocessing that is nearly standard for the LCS problem and has time and space complexity of O(ns + min {ds, lm}) and O(ns + d), respectively. This algorithm is particularly efficient when s (the alphabet size) is small. Different data structures are used to obtain variations of the basic algorithm that require different time and space complexities.en_US
dc.languageengen_US
dc.relation.ispartofJournal of information processingen_US
dc.titleFast algorithm for computing longest common subsequences of small alphabet sizeen_US
dc.typeArticleen_US
dc.identifier.emailChin, Francis YL:chin@cs.hku.hken_US
dc.identifier.authorityChin, Francis YL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0025531406en_US
dc.identifier.volume13en_US
dc.identifier.issue4en_US
dc.identifier.spage463en_US
dc.identifier.epage469en_US
dc.identifier.scopusauthoridChin, Francis YL=7005101915en_US
dc.identifier.scopusauthoridPoon, CK=7202673523en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats