Đang chuẩn bị liên kết để tải về tài liệu:
Automata technique for the LCS problem

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. | Journal of Computer Science and Cybernetics, V.35, N.1 (2019), 21–37 DOI 10.15625/1813-9663/35/1/13293 AUTOMATA TECHNIQUE FOR THE LCS PROBLEM NGUYEN HUY TRUONG School of Applied Mathematics and Informatics, Hanoi University of Science and Technology, Vietnam; truong.nguyenhuy@hust.edu.vn 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 classical dynamic programming algorithm proposed by Wagner and Fisher in 1974, respectively. Keywords. Automata; Dynamic programing; Knapsack shaking approach; Longest common subsequence; Parallel LCS. 1. INTRODUCTION The longest common subsequence (LCS) problem is a well-known problem in computer science [2, 3, 7, 8] and has many applications [1, 8, 14], especially in approximate pattern matching [8, 10, 12]. In 1972, authors V. Chvatal, D. A. Klarner and D. Knuth listed the problem of finding the longest common subsequence of the two strings in 37 selected combinatorial research problems [3]. The LCS problem for k strings (k > 2) is the NP-hard problem [7, 9, 11]. For the approximate pattern matching problem, the length of a longest common subsequence of two strings is used to compute the similarity between the two strings [10, 12]. Our work is concerned with the problem of finding the length of a longest subsequence of two strings of lengths m and n. In addition, our main objective is .