On The Longest Common Subsequence Problem- General And Variants

On The Longest Common Subsequence Problem-

General And Variants

A Thesis Submitted

in Partial Fulfillment of the Requirements

for the Degree of

Master of Technology

by

Sudheer Kumar Vootla

to the

DEPARTMENT OF COMPUTER SCIENCE&

ENGINEERING

INDIAN INSTITUTE OF TECHNOLOGY,KANPUR

July2006

Abstract

Let X and Y be any two sequences over an alphabetΣ,where each pair of elements inΣis comparable.The longest common increasing subse-quence(LCIS)problem is tofind an increasing subsequence S common to both X and Y of greatest length.

For any two sequences X and Y over an alphabetΣ,the longest common subsequence problem of X and Y is tofind a subsequence S common to both X and Y with greatest length.Unlike the LCIS problem where every pair of input alphabet is comparable,there is no such restriction in the LCS problem.Further the greatest common subsequence found in the LCIS must be strictly increasing,which need not be the case for LCS.

Let X,Y and P be any three sequences over an alphabetΣ.The con-strained longest common subsequence(CLCS)problem of X and Y with re-spect to P is tofind a longest common subsequence S of X and Y,such that P is a subsequence of S.

In this thesis we propose an algorithm for solving the LCIS problem. Our algorithm takes O((n +m)log log m)time and O(n +mσ)space. Here is the length of the LCIS andσis the size of the alphabet.

We also describe an algorithm for retrieving the longest common sub-sequence(LCS).Our algorithm takes O(m log n+d)time and O(n+|Σ|) space.

Finally,we propose an algorithm for the CLCS problem.Our algorithm takes O(r(m log n+d))time and O(n+α+|Σ|)space to retrieve the CLCS.

i

Acknowledgment

My foremost thanks go to Dr.Sanjeev Saxena for his invaluable supervision, guidance and support.He constantly encouraged me and gave many useful ideas throughout my Thesis work.Thank you sir,your guidance is of great help to me for completing my Thesis successfully.I would also like to thank Sitaram,Kiran and Siva Kumar for their help during many restless nights.

I would also like to take this opportunity to thank Lakshman,Swami along with my other lab mates Ravi Kumar,Sunil,Chandan,Abhijit,Sudeepa and Anjali for useful discussions and valuable suggestions.I must also thank our Department of Computer Science and IIT Kanpur for providing me world-class infrastructure with all the facilities and stimulating environment.

My special thanks to my parents who showered immense love on me and brothers for their affection and continuous support without which this work would not have been possible.

Sudheer Kumar Vootla

July2006

Indian Institute of Technology Kanpur

ii