Gamified challenge · KMP string matching
dna is a strand made of the letters A, C, G and T, and pattern is a gene (at least one letter). Write findAll(dna, pattern) that returns every index where the gene starts in the strand, in increasing order. Copies may overlap.
For dna = "AAAAAA" and pattern = "AAA" the answer is [0, 1, 2, 3]. If the gene never appears (or is longer than the strand), return [].
Strands can be thousands of bases long, so aim for linear time: when a partial match fails, reuse what you already know about the pattern instead of starting over.
This game is part of the paid plans. Sign in, then pick a plan to write your answer, watch it play out, and step through the algorithm with its guide.
Sign in with Google