Longest Common Substring with don't cares (Longest Common Subsequence)
Revision as of 10:18, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE: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 == <pre>$n$: length of the longer input string $m$: length of the shorter input string $r$:...")
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