Longest Common Substring with don't cares: Difference between revisions
Jump to navigation
Jump to search
(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$:...") |
No edit summary |
||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
$n$: length of the longer input string | |||
$m$: length of the shorter input string | $m$: length of the shorter input string | ||
$r$: length of the LCS | $r$: length of the LCS | ||
$s$: size of the alphabet | $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 | |||
$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 == | == Table of Algorithms == | ||
Latest revision as of 13:02, 15 February 2023
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