wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

maximal_common_subsequence (779B)

      1 # Maximal common subsequence (MCS)
      2 
      3 [maximal_common_subsequence] (MCS): common subsequence cannot be extended (inclusion in terms of [substrings])
      4 - formally: it is a common sequence and no supersequence is a common sequence
      5 - [longest_common_subsequence] is MCS but not necessarily vice-versa
      6 - [PTIME] to compute MCS for an unbounded number of multiple input strings: [hirota2023fast]
      7 
      8 [enumeration] in [conte2019polynomial]
      9 - but there is also a hardness result, Maximal Common Subsequence Enumeration is Hard #todo
     10 
     11 - warning! you can compute greedily a common sequence between 2 strings by extending it to the right
     12   - but it is not necessarily an MCS, it may still be possible to extend it by an insertion
     13 
     14 Up: [common_subsequence]
     15 
     16 See also: [longest_common_subsequence]