Automata Technique for The LCS Problem

Trường Huy Nguyễn
Author affiliations

Authors

  • Trường Huy Nguyễn School of Applied Mathematics and Informatics, Hanoi University of Science and Technology, Vietnam

DOI:

https://doi.org/10.15625/1813-9663/35/1/13293

Abstract

In this paper, we introduce two efficient algorithms in practice for computing the length of a longest common subsequence of two strings, using automata technique, in sequential and parallel ways. For two input strings of lengths m and n with m ≤ n, the parallel algorithm uses k processors (k ≤ m) and costs time complexity O(n) in the worst case, where k is an upper estimate of the length of a longest common subsequence of the two strings. These results are based on the Knapsack Shaking approach proposed by P. T. Huy et al. in 2002. Experimental results show that for the alphabet of size 256, our sequential and parallel algorithms are about 65.85 and 3.41m times faster than the standard dynamic programming algorithm proposed by Wagner and Fisher in 1974, respectively.

Metrics

Metrics Loading ...

Downloads

Published

18-03-2019

How to Cite

[1]
T. H. Nguyễn, “Automata Technique for The LCS Problem”, JCC, vol. 35, no. 1, p. 21–37, Mar. 2019.

Issue

Section

Computer Science