{CodeRoyale}
All challenges
Multiple ChoiceHard 30s

Naive vs KMP Pattern Matching

Naive string matching is O(n·m) while KMP is O(n+m). The speedup comes from:
Options
  1. 1Sorting the text and pattern first so matching can proceed linearly
  2. 2Running comparisons concurrently across several processor cores
  3. 3Using the LPS array to avoid re-checking characters that already matched
  4. 4Using a hash table to look up the pattern at every possible position
dsastringshard

Think you can answer under pressure?

Get matched and answer live questions in 3-minute 1v1 battles. Elo ranking, badge tiers and bragging rights on the line.

Play this in a 3-minute battle