File SubsequenceProblems.h

↰ Parent directory (ADS/string)

Four classic problems on the subsequences of sequences X, Y, Z of lengths n, m, l, relatives of the longest common subsequence [see File LongestCommonSubsequence.h], each by dynamic programming on the prefixes.

Definition (ADS/string/SubsequenceProblems.h)

Detailed Description

  • isInterleaving(): whether Z is a shuffle (an interleaving) of X and Y, the items of each in their order: D[ i ][ j ], whether Z[ 0 .. i + j ) interleaves X[ 0 .. i ) and Y[ 0 .. j ), is D[ i - 1 ][ j ] with x_{i-1} = z_{i+j-1} or D[ i ][ j - 1 ] with y_{j-1} = z_{i+j-1}; :math:` Theta( n m ) ` time and :math:` Theta( m ) ` space, one row of the table. Mansfield showed the problem NP-complete for the shuffle of an unbounded number of strings, and Warmuth and Haussler for the iterated shuffle of one string.

  • shortestCommonSupersequence(): the shortest sequence that has X and Y as subsequences, of length n + m - | LCS( X , Y ) |, read back from the table of the LCS: the common items once, the others in their order; :math:` Theta( n m ) ` time and space, while scsLength() keeps one row, :math:` Theta( m ) ` space. For an unbounded number of strings the problem is NP-hard (Maier).

  • subsequenceOccurrences(): the number of occurrences of P as a subsequence of T, the tuples of places j_1 < … < j_m with t_{j_k} = p_k: C[ i ][ j ] = C[ i - 1 ][ j ] + [ t_{i-1} = p_{j-1} ] C[ i - 1 ][ j - 1 ], :math:` Theta( n m ) ` time and one row updated from the right, :math:` Theta( m ) ` space; the count grows as fast as the binomial coefficient :math:` binom{n}{m} , and it is given modulo :math: 2^{64} `.

  • lcs3(): a longest common subsequence of three sequences, the table of lcs() in three dimensions, :math:` Theta( n m l ) ` time and space. The LCS of two of them and then of the third is not a solution: the longest pairwise one may leave out the items that the third shares. For k sequences the table has :math:` prod n_i ` entries, and the problem is NP-hard for an unbounded k (Maier).

Each function takes any sequence S with size(), operator[], push_back() and the comparison of its items; the overloads on std::string also take string literals.

The contracts [see File Contract.h]: the supersequence has X and Y as subsequences and the length of scsLength(), and lcs3() gives a subsequence of the three (audits). The functions are defined in SubsequenceProblems.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

  1. Maier, The complexity of some problems on subsequences and supersequences, Journal of the ACM 25(2), 322-336, 1978

  1. Mansfield, On the computational complexity of a merge recognition problem, Discrete Applied Mathematics 5(1), 119-122, 1983

    1. Warmuth, D. Haussler, On the complexity of iterated shuffle, Journal of Computer and System Sciences 28(3), 345-358, 1984

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions