File Download
There are no files associated with this item.
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: Fast algorithm for computing longest common subsequences of small alphabet size
Title  Fast algorithm for computing longest common subsequences of small alphabet size 

Authors  
Issue Date  1990 
Citation  Journal Of Information Processing, 1990, v. 13 n. 4, p. 463469 How to Cite? 
Abstract  Given 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(ml)) and O(n(nl)), 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 Identifier  http://hdl.handle.net/10722/152230 
ISSN  2015 SCImago Journal Rankings: 0.178 
DC Field  Value  Language 

dc.contributor.author  Chin, Francis YL  en_US 
dc.contributor.author  Poon, CK  en_US 
dc.date.accessioned  20120626T06:36:39Z   
dc.date.available  20120626T06:36:39Z   
dc.date.issued  1990  en_US 
dc.identifier.citation  Journal Of Information Processing, 1990, v. 13 n. 4, p. 463469  en_US 
dc.identifier.issn  03876101  en_US 
dc.identifier.uri  http://hdl.handle.net/10722/152230   
dc.description.abstract  Given 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(ml)) and O(n(nl)), 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.language  eng  en_US 
dc.relation.ispartof  Journal of information processing  en_US 
dc.title  Fast algorithm for computing longest common subsequences of small alphabet size  en_US 
dc.type  Article  en_US 
dc.identifier.email  Chin, Francis YL:chin@cs.hku.hk  en_US 
dc.identifier.authority  Chin, Francis YL=rp00105  en_US 
dc.description.nature  link_to_subscribed_fulltext  en_US 
dc.identifier.scopus  eid_2s2.00025531406  en_US 
dc.identifier.volume  13  en_US 
dc.identifier.issue  4  en_US 
dc.identifier.spage  463  en_US 
dc.identifier.epage  469  en_US 
dc.identifier.scopusauthorid  Chin, Francis YL=7005101915  en_US 
dc.identifier.scopusauthorid  Poon, CK=7202673523  en_US 