Introduction

The Naive Pattern Matching problem involves finding all occurrences of a pattern inside a text string.

Given:

  • a string text
  • a string pattern

the task is to:

  • find all starting indices
    where pattern
    occurs inside text

This is the most basic string matching algorithm.

This problem helps in understanding:

  • pattern matching
  • substring comparison
  • sequential traversal
  • string searching

Example

Input:text = "AABAACAADAABAABA"
pattern = "AABA"

Output:
0 9 12

Explanation:
Pattern occurs at:
index 0
index 9
index 12

Input:
text = "hello"
pattern = "ll"

Output:
2

Explanation:
Pattern starts at index 2.
Constraints
1 <= text.length,pattern.length <= 10^5
text and pattern
contain English characters

Approach : Naive Pattern Matching

Explanation

The idea is very simple:

  1. Start pattern comparison
    from every possible index
  2. Compare characters one by one
  3. If all characters match:
    • store index
  4. Continue traversal

This algorithm is called:

 Naive Pattern Matching

because it checks every possible position directly.

Steps

  1. Traverse possible starting positions.
  2. Compare pattern characters.
  3. If mismatch occurs:
    • move to next position
  4. If complete match found:
    • store current index
  5. Continue traversal.

Dry Run

Input:text = "AABAACAADAABAABA"pattern = "AABA"
Check index 0:
AABA
Match found
Store index 0

Check index 1:
ABAA
Mismatch found

Check index 9:
AABA
Match found
Store index 9

Check index 12:
AABA
Match found
Store index 12

Final Result:
0 9 12

Naive Pattern Matching Code

Complexity Analysis

Time Complexity: O(n * m)Explanation:Pattern comparison is performed
for every possible position.

Space Complexity: O(1)
Explanation:
No extra data structures are used
except result storage.

Edge Cases

  1. Pattern longer than text
  2. Pattern appears multiple times
  3. Pattern not present
  4. Pattern equals text
  5. Single character pattern

Why This Problem is Important

This problem helps in understanding:

  1. Basic pattern matching
  2. String traversal
  3. Sequential comparison
  4. Searching techniques
  5. Substring matching

It is the foundation for advanced algorithms like:

  • KMP Algorithm
  • Rabin Karp
  • Z Algorithm

Real-World Applications

Pattern matching concepts are used in:

  1. Search engines
  2. Text editors
  3. DNA sequence analysis
  4. Plagiarism detection
  5. Data filtering systems

Common Mistakes

  1. Incorrect loop bounds
  2. Index out of range errors
  3. Missing multiple matches
  4. Wrong substring comparison

Interview Tips

Interviewers often expect:

  1. Proper traversal explanation
  2. Time complexity analysis
  3. Pattern matching understanding

Always explain why traversal stops at:

 n - m

where:

  • n = text length
  • m = pattern length

Related Questions

  1. Implement strStr()
  2. KMP Algorithm
  3. Rabin Karp
  4. Minimum Window Substring
  5. Longest Substring Without Repeating Characters

Final Takeaway

The Naive Pattern Matching problem is a fundamental string searching problem that teaches sequential substring comparison techniques. Understanding this problem builds a strong foundation for advanced string matching and pattern searching interview problems.