Greedy Approach for Determining Longest Common Subsequence

By:
To add a paper, Login.

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
Stream: Technology in Education
Presentation Type: Paper Presentation in English
Paper: A paper has not yet been submitted.


Afroza Begum

Affiliation not supplied
Chittagong, Bangladesh


Ref: T08P0161