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)$) auxiliary	Exact	Deterministic
Rabin Karp	1987	$O(n)$	$O(max(n, sigma^k)$) auxiliary?	Exact	Deterministic

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination

References/Citation

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