Downloads: 0 | Views: 142

New Innovation and Idea | Computer Science & Engineering | India | Volume 11 Issue 10, October 2022

Twin Pairing Algorithm for Longest Common Subsequence

Sathya Narayanan P S

Abstract: Words are the building blocks of every language. Those words are built up by letters (characters). Those characters varying in their distribution based on the laws of permutation and combination give various Sequences. Those sequences might be either meaningful or even absurd in human language, but all of such Sequences are extremely meaningful when it comes to the world of computer processing and Analysis. Each of those sequences might carry something useful for any personnel from a specific domain. The Longest Common Subsequence which is shortly termed as the LCS is one such type of sequences where there are set of characters that appear in same order relatively but they might or might not be in contiguous form. This scenario occurs between more than one or multiple sequences. Such type of sequence is known to be an LCS or Longest Common Subsequence. This LCS is mostly used in the domains like linguistics, bioinformatics, Common sequence identification, biometrics, revision control systems/Version control systems (GIT). The Twin Pairing algorithm can find the LCS between strings at an efficient Space Complexity and Time Complexity when compared to the Traditional Algorithms such as Dynamic Programming approach and the recursion. The Twin Pairing algorithm can achieve the job of finding the LCS at an unbelievable Space Complexity of O(1) which is actually Constant Space Complexity and Time Complexity O (n log(m) + m log(n))where m and n are lengths of string1 and string2 among which LCS is to be obtained.

Keywords: Twin Pairing algorithm, Longest Common Subsequence, Constant Space Complexity, Space Complexity

Edition: Volume 11 Issue 10, October 2022,

Pages: 1009 - 1012