Naive Pattern Matching
Try every alignment and compare left to right, throwing away what was read at each mismatch.
Decision · step 2 of 6String Matching: Naive, every shift
Shift 0: pattern under "abcabc". 5 agree, then 'c' differs from 'd'. Move on to shift 1.
What you will see
The pattern slides one cell at a time under the text; matches and the first mismatch are marked.
Cost
| Best | O(n) |
|---|---|
| Average | O(n + m) |
| Worst | O(n * m) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Text and pattern cells announce index and character; each step announces the aligned positions, the comparison result and the shift.
Reduced motion: The pattern row snaps to its new alignment with a crossfade instead of sliding.
Before this
Related
Taught by the same lesson
String Matching covers these too, in the same run.