Back to all cards

Naive Text Search

Beginner Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

Naive search checks for each position in the text whether the pattern matches. On a mismatch, it shifts by 1.

Easy to understand, but slow on long texts with recurring patterns.

First hit: Find the Index of the First Occurrence in a String [1].

$$T[s:s+m]\stackrel{?}{=}P$$

Where used

Small patterns, one-time searches, teaching purposes. Replace in hot paths with indexOf, automata, or index structures.

Depth

The naive text search aligns the pattern one by one at each possible starting position of the text. For each alignment, characters are compared from left to right until a difference is found or the entire pattern is confirmed.

After a difference, the method shifts the pattern by one position and starts the comparison again. Recognized matches are not systematically utilized. The method is still valuable because it is short, correct, and often sufficient for small inputs or short patterns.

Difficulty levels

Check all alignments of a pattern in a short text.
Understand early exits for unequal first characters.
Construct inputs that cause many repeated comparisons.

Pitfalls

The last valid starting position can easily be skipped by an incorrect loop boundary. Empty patterns also require an explicitly chosen semantics so that implementation and tests match.

Sources

[1]https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/Return to text

University approvals: 0

Tasks

Question 1

How far does the naive search typically shift upon a mismatch?

to determine the pattern length

at 1

um n

not at all

Question 2

Why does the naive search for a late mismatch restart at the next text position?

It does not possess any pre-calculated information about usable pattern structure.

The text may only be read once.

Every incorrect comparison proves that the pattern does not occur anywhere.

The pattern length decreases after each comparison.

Question 3

Implement a naive text search. Return the first start index of the pattern or -1.

Hint

String.length() returns the length, charAt(i) a character. Characters are compared with == or !=.

class NaiveSearch {
  static int indexOfNaive(String text, String pat) {
    // TODO
    return -1;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithms and Data Structures
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy