Longest Common Substring with don't cares (Longest Common Subsequence)

From Algorithm Wiki
Revision as of 12:02, 15 February 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


Find the length of the longest common substring of two strings S and T, where S is a binary string and T is is a binary string and additional * characters that can match either 0 or 1.

Related Problems

Generalizations: Longest Common Subsequence


$n$: length of the longer input string

$m$: length of the shorter input string

$r$: length of the LCS

$s$: size of the alphabet

$p$: the number of dominant matches (AKA number of minimal candidates), i.e. the total number of ordered pairs of positions at which the two sequences match

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem Implication Year Citation Reduction
CNF-SAT if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$
2014 https://link.springer.com/chapter/10.1007/978-3-662-43948-7_4 link