Foundations — Naive pattern matching — O(nm)

This page builds every piece of notation the parent Naive pattern matching note leans on, starting from "what is a string" and ending at "why $O(nm)$". If a symbol appears on the parent page, it is defined here first, with a picture.

1. What is a string, and what is an index?

A character is one single symbol — one bead. A string is the whole necklace.

To talk about one specific bead, we number the positions. In almost all of computing we start counting at 0, not 1. The number of a position is called its index.

We write $T[i]$ to mean "the character of string $T$ sitting at index $i$." The square brackets are read aloud as "at index". So $T[0]$ is the first character, $T[1]$ the second, and so on.

2. Length, and the symbols $n$ and $m$

The parent note gives two strings special names and two lengths special letters:

Length is ::: n for the text, m for the pattern

3. Slice notation: $T[a\dots b]$

The parent writes $T[s\dots s+m-1]$. This is slice (or substring) notation.

Why does the parent write $T[s\dots s+m-1]$? Because it wants a chunk of the text that is exactly $m$ characters long, starting at index $s$. Count them: from $s$ to $s+m-1$ inclusive is $(s+m-1)-s+1=m$ characters — the same length as the pattern, so the two can be compared bead-for-bead.

A slice's length is ::: (b - a + 1) characters for T[a..b]

4. The shift $s$ and why it stops at $n-m$

The parent claims there are exactly $n-m+1$ candidate shifts, from $s=0$ to $s=n-m$. Let us see why the last legal shift is $n-m$, not something else.

Counting the whole-number shifts $0,1,2,\dots ,n-m$ gives $==n-m+1==$ of them. This is the number of times the outer loop runs.

5. What "$=$" means between two slices (a valid shift)

The parent's definition of a match is $T[s\dots s+m-1]=P[0\dots m-1].$

So "$=$" here is not one comparison — it is a promise about all $m$ positions at once. To test that promise, we must walk through the positions one at a time. That walk is exactly the inner loop.

A shift $s$ where this equality holds is called a valid shift — the thing the algorithm reports.

6. The offset $j$ — the inner counter

The pseudocode introduces $j$: the position within the pattern we are currently checking.

The condition j == m is the signal "the inner loop ran to completion". Since $j$ counts up from $0$, reaching the value $m$ means it checked indices $0$ through $m-1$ — all of them.

7. The symbols behind $O(nm)$

The parent's time bound uses the letter $O$ and the product $nm$. You do not need the full theory (see Big-O Notation), only these plain meanings:

Why does $n\times m$ appear? Multiply the two loop counts:

Prerequisite map

Equipment checklist

If you can answer each of these, you are ready for the parent page.

Connections

• Parent: Naive pattern matching — everything here feeds it.
• Big-O Notation — the meaning of the $O(nm)$ ceiling.
• Substring Search Problem — the larger problem these symbols describe.
• Sliding Window Technique — the "slide the pattern by increasing $s$" picture generalized.