Overview
Naive String Search aligns the pattern with each text position and compares characters until a mismatch or full match.
FoundationSource checked
Naive String Search
Finds a pattern by checking every possible starting position.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Beginner
- Family
- Brute Force String Matching
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
pattern comparisonstring sequencesequential scanbrute force string matchingsequence scanpattern statematch verification
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(nm)
Worst
O(nm)
Space
O(1)
When to Use
- Use Naive String Search when you need to test each possible alignment.
- Use it for small text search with inputs like text.
- Use it when exact, fuzzy, or structured patterns must be found in sequences.
- Use it when the Brute Force String Matching tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when preprocessing cost is larger than a one-off simple scan.
- Avoid it when the required output is not match positions.
What It Does
- Tests each possible alignment
- Compares pattern characters directly
Use Cases
- Small text search
- Teaching string matching
- Simple exact matching
Inputs
- Text
- Pattern
Outputs
- Match positions
Key Formulas (1)
Alignment match
match at i if pattern[j] = text[i + j] for every j
match at i if pattern[j] == text[i + j] for every jChecks whether the pattern matches the text at one starting position.
Pseudocode
- 1.Place the pattern at the first text position
- 2.Compare characters from left to right
- 3.Record a match if every character matches
- 4.Move the pattern one position right
- 5.Repeat until no full alignment remains
Canonical Example
- Input
- text = "abracadabra", pattern = "abra"
- Output
- matches at positions [0, 7]
- Explanation
- The pattern matches the first four characters and the final four characters.
Implementation Notes
- Try every valid alignment from 0 through text length minus pattern length.
- Compare characters until a mismatch or full match occurs.
- Define empty-pattern and overlapping-match behavior explicitly.
Common Pitfalls
- Repeating many comparisons on inputs with overlapping partial matches.
- Forgetting to handle an empty pattern according to the chosen API contract.
- Reporting only the first match when all matches, including overlaps, are required.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow a pattern sliding one character at a time over text.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Place the pattern at the first text position
string-alignmentNotes
Naive search is easiest to verify, but repeated partial matches can make it slow.
Sources (1)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference covering Naive String Search recurrences, automata/indexing structures, or exact/approximate matching role.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pagePrerequisite ofKnuth-Morris-Pratt
KMP improves on naive search by reusing prefix information.
Alternative toRabin-Karp
Both search for patterns in text with different matching strategies.
Related Algorithms
Tags
Pattern MatchingStringsLinear ScanClassic