The Longest Common Subsequence Problem A Finite Automata Approach
Bořivoj Melichar6 
and Tomáš Polcar6
| (6) |
Department of Computer Science and Engineering Faculty of Electrical Engineering, Czech Technical University, Karlovo nám. 13, 121 35 Prague 2, Czech Republic |
Abstract
A new algorithm that creates a common subsequence automaton for a set of strings is presented. Moreover, it is shown that
a longest common subsequence of two strings over a constant alphabet can be found in
time, where |
A| is the size of the alphabet, |
S
i
| is the length of the input string
i, and |
S
i
|
a is the number of occurrences of
a ∈ A in
S
i
.
This research has been partialy supported by the Ministry of Education, Youth, and Sports of the Czech Republic under research
program No. J04/98:212300014 (Research in the area of information technologies and cummunications) and by Grant Agency of
Czech Republic grant No. 201/01/1433.
References secured to subscribers.