Polynomial Delay Enumeration of MCS
Discover the innovative approach of listing distinct Maximal Common Subsequences (MCS) efficiently between two strings through a graph-based algorithm. This algorithm tackles the challenge of preventing repeated listings of the same MCS, offering a significant advancement in this field of study.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Polynomial-Delay Enumeration of Maximal Common Subsequences Alessio Conte, Roberto Grossi, Giulia Punzi and Takeaki Uno String Processing and Information Retrieval, 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7 9, 2019, pp. 189-202 Presenter: Du-Cheng Wu Date: Oct. 15, 2019
Abstract A Maximal Common Subsequence (MCS) between two strings X and Y is an inclusion-maximal subsequence of both X and Y. MCSs are a natural generalization of the classical concept of Longest Common Subsequence (LCS), which can be seen as a longest MCS. We study the problem of efficiently listing all the distinct MCSs between two strings. As discussed in the paper, this problem is algorithmically challenging as the same MCS cannot be listed multiple times: for example, dynamic programming [Fraser et al., CPM 1998] incurs in an exponential waste of time, and a recent algorithm for finding an MCS [Sakai, CPM 2018] does not seem to immediately extend to listing. We follow an alternative and novel graph-based approach, proposing the first output-sensitive algorithm for this problem: it takes polynomial time in n per MCS found, where n=max{|X|,|Y|} , with polynomial preprocessing time and space.
Maximal common subsequence(MCS) X = ACEDF Y = AEDCF LCS = AEDF MCS = AEDF, ACF
Complexity O(n ( +log n)) polynomial delay O(n2( +log n)) preprocessing time O(n2) space
