Greedy Approach for Determining Longest Common Subsequence
The problem of finding the longest common subsequence (LCS) of two given sequences is well studied and has a lot of applications in various fields, DNA or protein alignments, file comparison, speech recognition, gas chromatography, etc. Over the last two decades, many efficient algorithms have been designed to solve LCS problem. This paper describes a simple greedy approach to find LCS. Given two strings X and Y of length m and n, an algorithm is presented which determines Longest Common Subsequences in O(m) time with O(nlogs) preprocessing time, where s is the distinct symbols appearing in string Y.
Keywords: Algorithms, Alphabet, Longest Common Subsequences, Greedy algorithm
Affiliation not supplied