RI UFLA (Universidade Federal de Lavras) >
Revistas UFLA >
Infocomp >

Please use this identifier to cite or link to this item: http://repositorio.ufla.br/jspui/handle/1/9941

Title: Computing a longest common subsequence of two strings when one of them is run length encoded
???metadata.dc.creator???: Ahsan, Shegufta Bakht
Moosa, Tanaeem M.
Rahman, M. Sohel
Shahriyar, Shampa
Keywords: Algorithms
Longest common subsequence
Run length encoded strings
Maior subsequência comum
String de codificação run-length
Publisher: Editora da UFLA
???metadata.dc.date???: 1-Sep-2011
Citation: AHSAN, S. B. et al. Computing a longest common subsequence of two strings when one of them is run length encoded. INFOCOMP: Journal of Computer Science, Lavras, v. 10, n. 3, p. 48-55, Sept. 2011.
Abstract: Given two strings, the longest common subsequence (LCS) problem computes a common subsequence that has the maximum length. In this paper, we present new and efficient algorithms for solving the LCS problem for two strings one of which is run length encoded (RLE). We first present an algorithm that runs in O(gN) time, where g is the length of the RLE string and N is the length of uncompressed string. Then based on the ideas of the above algorithm we present another algorithm that runs in O(Rlog(log g)+N) time, where R is the total number of ordered pairs of positions at which the two strings match. Our first algorithm matches the best algorithm in the literature for the same problem. On the other hand, for R < gN/ log(log)g, our second algorithm outperforms the best algorithms in the literature.
Other Identifiers: http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/337
???metadata.dc.language???: eng
Appears in Collections:Infocomp

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

View Statistics


DSpace Software Copyright © 2002-2010  Duraspace - Feedback