The Frequent Words Problem (The Frequent Words Problem)

Description

Given a string of length $n$ and in input integer $k$, determine the most frequent $k$-mers in the string, i.e. the most frequent words of length $k$.

Parameters

$n$: length of string

$k$: length of words

$\sigma$: size of alphabet

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Naive solution	1940	$O(n)$	$O(max(n, \sigma^k)$)	Exact	Deterministic
Rabin Karp	1987	$O(n)$	$O(max(n, \sigma^k)$)?	Exact	Deterministic

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff

References/Citation

http://bioinformaticsalgorithms.com/data/debugdatasets/replication/FrequentWordsProblem.pdf