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

Jump to navigation
Jump to search

## 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