Longest Common Substring in Pattern Matching
Maahin Gupta, Senthil Kumar K, Ayush Joshi · 2024
The longest common substring (LCS) identification has many applications in Pattern matching, Automata Theory, Bioinformatics, especially in DNA arrangement examination. The LCS issue looks for the longest shared substring over a given set of strings. We will look at strategies beginning with the conventional approach utilizing generalized addition trees increased with least common precursor inquiries, taken after by a novel strategy utilizing postfix trees combined with productive union-find information structures, advertising a direct linear-time calculation versatile to space-efficient compressed postfix tree representations. Furthermore, we will cover variations of these strategies pointed at lessening space utilization whereas keeping up competitive running times, dissecting how they use compressed records and union-find structures to possibly outflank prior arrangements in terms of time and space complexity. All through the assessment, we will consider each method utilize of headways in compressed content ordering methods, evaluating their execution, versatility, and versatility to large-scale genomic datasets where space productivity is vital. By comparing these approaches, we point to distinguish the most viable and effective arrangement for the LCS issue, highlighting the strategy that best equalizations execution, space effectiveness, and flexibility for different bioinformatics applications.