ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Twin Pairing Algorithm for Longest Common Subsequence

Journal: International Journal of Science and Research (IJSR) (Vol.11, No. 10)

Publication Date:

Authors : ;

Page : 1009-1012

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

Source : Downloadexternal Find it from : Google Scholarexternal

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.

Last modified: 2025-09-22 21:31:24