Longest Common Substring with don't cares

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.

Parameters

  • nn: length of the longer input string
  • mm: length of the shorter input string
  • rr: length of the LCS
  • ss: size of the alphabet
  • pp: 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

Related Problems

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 2 of 2 reductions

Other relevant algorithms

Insuffient Data to display table