View source for Frequent Words with Mismatches Problem

{{DISPLAYTITLE:Frequent Words with Mismatches Problem (Frequent Words with Mismatches Problem)}}
== 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 == 

<pre>n: length of string
k: length of words
d: number of allowed mismatches
sigma: size of alphabet</pre>

== Table of Algorithms == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Naive solution ( Frequent Words with Mismatches Problem)|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 == 

[[File:Frequent Words with Mismatches Problem - Time.png|1000px]]

== Space Complexity graph == 

[[File:Frequent Words with Mismatches Problem - Space.png|1000px]]

== Pareto Decades graph == 

[[File:Frequent Words with Mismatches Problem - Pareto Frontier.png|1000px]]