The longest common subsequence problem a finite automata approach

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 φ (|A|(|S1| + |S2| + Σa∈A|S1|a|S2|S 2|a)) time, where |A| is the size of the alphabet, |Si| is the length of the input string i, and |Si|a is the number of occurrences of a ∈ A in Si.