A greedy approach for computing longest common subsequences

Afroza Begum
Department of Computer Science and Engineering, International Islamic University
Chittagong, Chittagong, Bangladesh.

\(^{1}\)Corresponding Author: afrozactg@yahoo.com

Copyright © 2008 Afroza Begum. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Published: December, 2008.

Abstract

This paper presents an algorithm for computing Longest Common Subsequences for two sequences. Given two strings \(X\) and \(Y\) of length \(m\) and \(n\), we present a greedy algorithm, which requires \(O(n log s)\) preprocessing time, where s is distinct symbols appearing in string \(Y\) and \(O(m)\) time to determines Longest Common Subsequences.

Keywords:

Algorithms, alphabet, longest common subsequences, greedy algorithm.