Frequent Words with Mismatches Problem (Frequent Words with Mismatches Problem)

From Algorithm Wiki
Jump to navigation Jump to search

Description

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

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Naive solution 1940 $O(n*f_{bin}(sigma-{1}, k, d)$) where f_{bin}(x, y, z) = sum_{i=0}^z C(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 C(y, i)*x^i Exact Deterministic

Time Complexity Graph

Frequent Words with Mismatches Problem - Time.png