2020/09/07 by Jin Cao, Cao, Jin, Dewei Zhong +1
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2009.03352
openalex publication_date 2020/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Finding the common subsequences of L multiple strings has many applications in the area of bioinformatics, computational linguistics, and information retrieval. A well-known result states that finding a Longest Common Subsequence (LCS) for L strings is NP-hard, e.g., the computational complexity is exponential in L. In this paper, we develop a randomized algorithm, referred to as \em Random-MCS, for finding a random instance of Maximal Common Subsequence (MCS) of multiple strings. A common subsequence is \em maximal if inserting any character into the subsequence no longer yields a common subsequence. A special case of MCS is LCS where the length is the longest. We show the complexity of our algorithm is linear in L, and therefore is suitable for large L. Furthermore, we study the occurrence probability for a single instance of MCS and demonstrate via both theoretical and experimental studies that the longest subsequence from multiple runs of \em Random-MCS often yields a solution to LCS.