Determining Disjoint Longest Common Subsequences
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. In this paper, a variant of this problem is introduced. Given two strings of length of m and n, m>=n , an algorithm is presented which determines all possible Disjoint Longest Common Subsequences. Here, the maximum number of Disjoint Longest Common Subsequences are computed, where no symbol found identical in between in any two LCSs. Symbols in different positions are considered to be different. The algorithm presented here uses multistage graph structure.
Keywords: Algorithms, Disjoint Longest Common Subsequence, Disjoint Longest Increasing Subsequence, Multistage Graph
Affiliation not supplied