Frequent Words with Mismatches Problem

Given two strings, determine the most frequent substring with at most $k$ mismatches, where mismatches are not counted towards the length of the substring.

Parameters

$n$ : length of string
$k$ : length of words
$d$ : number of allowed mismatches
$\sigma$ : size of alphabet

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

				See more
Naive solution	1940	$O(n f_{bin}(\sigma-1, k, d))$ where $f_{bin}(x, y, z) = \sum_{i=0}^z \binom{y}{i}x^i$	$O(max(n f_{bin}(\sigma-1, k, d), \sigma^k))$ auxiliary where $f_{bin}(x, y, z) = \sum_{i=0}^z \binom{y}{i}x^i$

Reductions Table

Insuffient Data to display table

Other relevant algorithms