The Frequent Words Problem

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

				See more
Rabin-Karp (hashing-based)	1987	$O(k(n-k))$	$O(\max(n, \sigma^k))$
Naive solution	1940	$O(k(n-k)^2)$	$O(\max(n, \sigma^k))$

Reductions Table

Insuffient Data to display table

Other relevant algorithms