TAILIEUCHUNG - 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. | Journal of Computer Science and Cybernetics 2019 21-37 DOI 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 Crossref Similarity Check 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 and 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 planning to deal with the approximate .

• Toán học
• Dynamic programing
• Knapsack shaking approach
• Longest common subsequence
• Parallel LCS
• Classical dynamic programming
• Object Oriented Programing
• Lecture Object Oriented Programing
• Programming languages
• Data structures
• Type wrapper classes
• Dynamic memory allocation
• lập trình quy hoạch động
• phương pháp thực hiện
• phương pháp đệ quy
• phạm vi ứng dụng
• Multi objective optimization
• Multi level programing
• Dynamic leader follower model
• Lack of central authority
• Multi level modeling
• Supplemental irrigation
• On farm reservoir
• Rainfed agriculture
• Water management
• Automata technique
• Soil moisture dynamics
• Yield response