International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Call for Papers | Fully Refereed | Open Access | Double Blind Peer Reviewed

ISSN: 2319-7064

Downloads: 0 | Views: 80

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

How to Download this Article?

Type Your Valid Email Address below to Receive the Article PDF Link

Verification Code will appear in 2 Seconds ... Wait