String Pattern Matching Naive in DSA Java

Mental Model

Check every possible place in the text to see if the pattern matches exactly.

Analogy: Like looking for a small word in a big book by checking every word one by one until you find a match.

Text:  H  E  L  L  O  W  O  R  L  D
Index: 0  1  2  3  4  5  6  7  8  9
Pattern:     P  A  T  T  E  R  N
               ↑
               Checking here

Dry Run Walkthrough

Input: text: "ABABABC", pattern: "ABABC"

Goal: Find the starting index where the pattern "ABABC" appears in the text.

Step 1: Check text starting at index 0 for pattern match

Text: A B A B A B C
       ↑
Pattern: A B A B C
         ↑

Why: Start checking from the beginning of the text

Step 2: Compare characters one by one at index 0

Match A==A, B==B, A==A, B==B, A!=C at pattern index 4
Mismatch found

Why: Mismatch means pattern does not match here, move to next index

Step 3: Check text starting at index 1 for pattern match

Text: A B A B A B C
         ↑
Pattern: A B A B C
           ↑

Why: Try matching pattern starting from next position

Step 4: Compare characters one by one at index 1

Mismatch at first character: B != A

Why: No match here, move to next index

Step 5: Check text starting at index 2 for pattern match

Text: A B A B A B C
           ↑
Pattern: A B A B C
             ↑

Why: Try matching pattern starting from index 2

Step 6: Compare characters one by one at index 2

Match A==A, B==B, A==A, B==B, C==C
Full match found

Why: Pattern matches completely starting at index 2

Result:

Pattern found at index 2

Annotated Code

DSA Java

public class NaivePatternMatching {
    public static int naiveSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break; // mismatch found, stop checking this position
                }
            }
            if (j == m) {
                return i; // full match found at index i
            }
        }
        return -1; // pattern not found
    }

    public static void main(String[] args) {
        String text = "ABABABC";
        String pattern = "ABABC";
        int result = naiveSearch(text, pattern);
        if (result == -1) {
            System.out.println("Pattern not found");
        } else {
            System.out.println("Pattern found at index " + result);
        }
    }
}

for (int i = 0; i <= n - m; i++) {

Try every possible starting position in text where pattern can fit

for (j = 0; j < m; j++) {

Check each character of pattern against text at current position

if (text.charAt(i + j) != pattern.charAt(j)) { break; }

Stop checking this position if any character mismatches

if (j == m) { return i; }

If all characters matched, return the starting index

Output

Pattern found at index 2

Complexity Analysis

Time: O(n*m) because for each of the n-m+1 positions in text, we compare up to m characters

Space: O(1) because no extra space is used except variables

vs Alternative: Compared to advanced algorithms like KMP which run in O(n), naive is slower but simpler to implement

Edge Cases

Empty pattern

Returns 0 immediately since empty pattern matches at start

DSA Java

for (int i = 0; i <= n - m; i++) {

Pattern longer than text

Loop does not run, returns -1 meaning no match

DSA Java

for (int i = 0; i <= n - m; i++) {

Pattern not in text

Returns -1 after checking all positions

DSA Java

return -1; // pattern not found

When to Use This Pattern

When asked to find if a small pattern exists inside a larger text and no preprocessing is required, naive pattern matching is the first simple approach to try.

Common Mistakes

Mistake: Not stopping inner loop on mismatch and continuing to compare unnecessary characters
Fix: Add a break statement immediately when a mismatch is found

Mistake: Looping beyond the last possible start index causing index out of bounds
Fix: Ensure outer loop runs only until n - m inclusive

Summary

Checks every possible position in the text to find the pattern by comparing characters one by one.

Use when pattern matching is needed and input sizes are small or simplicity is preferred over speed.

The key insight is to try matching the pattern at each position until a full match is found or all positions are checked.

Practice

1. What is the main idea behind the naive string pattern matching algorithm?

easy

A. Preprocess the pattern to skip unnecessary comparisons

B. Use a hash function to find the pattern quickly

C. Sort the text and pattern before matching

D. Check every possible position in the text to see if the pattern matches

Solution

1. Step 1: Understand the naive approach

   The naive algorithm tries to match the pattern starting at every position in the text.

2. Step 2: Compare pattern characters at each position

   At each position, it compares characters one by one until a mismatch or full match is found.

3. Final Answer:

   Check every possible position in the text to see if the pattern matches -> Option D

4. Quick Check:

   Naive = Check all positions [OK]

Hint: Naive means try all positions one by one [OK]

Common Mistakes:

• Thinking naive uses hashing
• Assuming it preprocesses pattern
• Confusing with advanced algorithms like KMP

2. Which of the following is the correct syntax to start a loop for naive pattern matching in Java if text length is n and pattern length is m?

easy

A. for (int i = 0; i <= n; i++)

B. for (int i = 0; i <= n - m; i++)

C. for (int i = 0; i < m; i++)

D. for (int i = 0; i < n; i++)

Solution

1. Step 1: Determine valid start positions

   Pattern of length m can only start at positions 0 to n-m in text of length n.

2. Step 2: Write loop condition

   Loop must run from i = 0 to i <= n - m to avoid index out of bounds.

3. Final Answer:

   for (int i = 0; i <= n - m; i++) -> Option B

4. Quick Check:

   Loop till n-m inclusive [OK]

Hint: Loop till n - m inclusive to fit pattern [OK]

Common Mistakes:

• Looping till n causes index errors
• Looping till m is too short
• Using < instead of <= for last position

3. What will be the output of the following Java code snippet?

String text = "abcabcabc";
String pattern = "abc";
int count = 0;
for (int i = 0; i <= text.length() - pattern.length(); i++) {
  int j;
  for (j = 0; j < pattern.length(); j++) {
    if (text.charAt(i + j) != pattern.charAt(j)) {
      break;
    }
  }
  if (j == pattern.length()) {
    count++;
  }
}
System.out.println(count);

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Identify pattern occurrences

   Pattern "abc" appears at positions 0, 3, and 6 in text "abcabcabc".

2. Step 2: Count matches in nested loops

   Each full match increments count. Total matches found = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Pattern "abc" occurs 3 times [OK]

Hint: Count full matches by checking all positions [OK]

Common Mistakes:

• Counting overlapping matches incorrectly
• Breaking loop too early
• Off-by-one errors in loop conditions

4. Find the error in this naive pattern matching code snippet:

String text = "hellohello";
String pattern = "hello";
for (int i = 0; i < text.length() - pattern.length(); i++) {
  int j;
  for (j = 0; j < pattern.length(); j++) {
    if (text.charAt(i + j) != pattern.charAt(j)) {
      break;
    }
  }
  if (j == pattern.length()) {
    System.out.println("Pattern found at index " + i);
  }
}

medium

A. Loop condition should be i <= text.length() - pattern.length()

B. Inner loop should start from j = 1

C. Pattern length should be text length

D. No error, code is correct

Solution

1. Step 1: Check outer loop range

   Loop runs from i = 0 to i < text.length() - pattern.length(), missing last valid start index.

2. Step 2: Correct loop condition

   It should be i <= text.length() - pattern.length() to include last possible match.

3. Final Answer:

   Loop condition should be i <= text.length() - pattern.length() -> Option A

4. Quick Check:

   Include last index with <= [OK]

Hint: Use <= to include last valid start index [OK]

Common Mistakes:

• Using < instead of <= in outer loop
• Starting inner loop from wrong index
• Confusing pattern and text lengths

5. Given a text and a pattern, how can you modify the naive string pattern matching algorithm to count overlapping occurrences of the pattern in the text? For example, text = "aaaaa" and pattern = "aaa" should count 3 occurrences.

Which change is correct?

hard

A. Use a hash function to detect overlaps

B. After finding a match at index i, increment i by pattern length

C. After finding a match at index i, increment i by 1 instead of pattern length

D. Skip checking overlapping positions entirely

Solution

1. Step 1: Understand overlapping matches

   Overlapping means pattern can start inside a previous match, so we must check every next position.

2. Step 2: Adjust index increment

   Instead of jumping by pattern length after a match, increment index by 1 to check next position.

3. Final Answer:

   After finding a match at index i, increment i by 1 instead of pattern length -> Option C

4. Quick Check:

   Increment by 1 to count overlaps [OK]

Hint: Increment index by 1 after match to count overlaps [OK]

Common Mistakes:

• Skipping overlapping positions by jumping pattern length
• Using hashing which is unrelated here
• Ignoring overlaps completely