Computing the longest common subsequence of two run-length encoded strings

Yoshifumi Sakai

doi:10.1007/978-3-642-35261-4_23

Computing the longest common subsequence of two run-length encoded strings

Yoshifumi Sakai

AGR - Agricultural Bioscience

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Citations (Scopus)

Abstract

The present article reveals that the problem of finding the longest common subsequence of two strings given in run-length encoded form can be solved in O(mnlog log min(m, n, M/m, N/n, X)) time, where one input string is of length M with m runs, the other is of length N with n runs, and X is the average difference between the length of a run from one input string and that of a run from the other.

Original language	English
Title of host publication	Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
Publisher	Springer Verlag
Pages	197-206
Number of pages	10
ISBN (Print)	9783642352607
DOIs	https://doi.org/10.1007/978-3-642-35261-4_23
Publication status	Published - 2012
Event	23rd International Symposium on Algorithms and Computation, ISAAC 2012 - Taipei, Taiwan, Province of China Duration: 2012 Dec 19 → 2012 Dec 21

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7676 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Symposium on Algorithms and Computation, ISAAC 2012
Country/Territory	Taiwan, Province of China
City	Taipei
Period	12/12/19 → 12/12/21

Access to Document

10.1007/978-3-642-35261-4_23

Cite this

Sakai, Y. (2012). Computing the longest common subsequence of two run-length encoded strings. In Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings (pp. 197-206). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7676 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-35261-4_23

@inproceedings{2592b28795b54a54ba7a61f63bdebf80,

title = "Computing the longest common subsequence of two run-length encoded strings",

abstract = "The present article reveals that the problem of finding the longest common subsequence of two strings given in run-length encoded form can be solved in O(mnlog log min(m, n, M/m, N/n, X)) time, where one input string is of length M with m runs, the other is of length N with n runs, and X is the average difference between the length of a run from one input string and that of a run from the other.",

author = "Yoshifumi Sakai",

year = "2012",

doi = "10.1007/978-3-642-35261-4_23",

language = "English",

isbn = "9783642352607",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "197--206",

booktitle = "Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings",

address = "Germany",

note = "23rd International Symposium on Algorithms and Computation, ISAAC 2012 ; Conference date: 19-12-2012 Through 21-12-2012",

}

Sakai, Y 2012, Computing the longest common subsequence of two run-length encoded strings. in Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7676 LNCS, Springer Verlag, pp. 197-206, 23rd International Symposium on Algorithms and Computation, ISAAC 2012, Taipei, Taiwan, Province of China, 12/12/19. https://doi.org/10.1007/978-3-642-35261-4_23

Computing the longest common subsequence of two run-length encoded strings. / Sakai, Yoshifumi.
Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. Springer Verlag, 2012. p. 197-206 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7676 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Computing the longest common subsequence of two run-length encoded strings

AU - Sakai, Yoshifumi

PY - 2012

Y1 - 2012

N2 - The present article reveals that the problem of finding the longest common subsequence of two strings given in run-length encoded form can be solved in O(mnlog log min(m, n, M/m, N/n, X)) time, where one input string is of length M with m runs, the other is of length N with n runs, and X is the average difference between the length of a run from one input string and that of a run from the other.

AB - The present article reveals that the problem of finding the longest common subsequence of two strings given in run-length encoded form can be solved in O(mnlog log min(m, n, M/m, N/n, X)) time, where one input string is of length M with m runs, the other is of length N with n runs, and X is the average difference between the length of a run from one input string and that of a run from the other.

UR - http://www.scopus.com/inward/record.url?scp=84871550017&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84871550017&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-35261-4_23

DO - 10.1007/978-3-642-35261-4_23

M3 - Conference contribution

AN - SCOPUS:84871550017

SN - 9783642352607

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 197

EP - 206

BT - Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings

PB - Springer Verlag

T2 - 23rd International Symposium on Algorithms and Computation, ISAAC 2012

Y2 - 19 December 2012 through 21 December 2012

ER -

Sakai Y. Computing the longest common subsequence of two run-length encoded strings. In Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. Springer Verlag. 2012. p. 197-206. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-35261-4_23

Computing the longest common subsequence of two run-length encoded strings

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this