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

Description

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

Parameters

$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

References/Citation

https://link.springer.com/chapter/10.1007/978-3-662-43948-7_4