wiki_research

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

maximal_common_subsequence (689B)

      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_maximal_common_subsequence]
      9 
     10 - warning! you can compute greedily a common sequence between 2 strings by extending it to the right
     11   - but it is not necessarily an MCS, it may still be possible to extend it by an insertion
     12 
     13 Up: [common_subsequence]
     14 
     15 See also: [longest_common_subsequence]