Find Patterns Forming Clumps in a String solved by 2461

July 29, 2015, 12:29 a.m. by Rosalind Team

Given integers L and t, a string Pattern forms an (L, t)-clump inside a (larger) string Genome if there is an interval of Genome of length L in which Pattern appears at least t times. For example, $\color{green}{\text{TGCA}}$ forms a (25,3)-clump in the following Genome: $\text{gatcagcataagggtccc}\color{green}\textbf{TGCA}\color{black}\text{A}\color{green}\textbf{TGCA}\color{black}\text{TGACAAGCC}\color{green}\textbf{TGCA}\color{black}\text{gttgttttac}$.

Clump Finding Problem

Find patterns forming clumps in a string.

Given: A string Genome, and integers k, L, and t.

Return: All distinct k-mers forming (L, t)-clumps in Genome.

Sample Dataset

CGGACTCGACAGATGTGAAGAAATGTGAAGACTGAGTGAAGAGAAGAGGAAACACGACACGACATTGCGACATAATGTACGAATGTAATGTGCCTATGGC
5 75 4

Sample Output

CGACA GAAGA AATGT

Extra Datasets

Please login to solve this problem.