String Pattern Matching Naive in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Pattern Matching

What is the output of the following Java code that uses naive string pattern matching to find all occurrences of a pattern in a text?

DSA Java

public class NaivePatternMatching {
    public static void main(String[] args) {
        String text = "abracadabra";
        String pattern = "abra";
        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.print(i + " ");
            }
        }
    }
}

A 3 7

B 0 7

C 7

D 0 3 7

💡 Hint

Look for all starting indices where the pattern matches exactly in the text.

The pattern "abra" appears twice in "abracadabra": starting at index 0 and index 7. The code prints these indices separated by spaces.

🧠 Conceptual

intermediate

Number of Comparisons in Worst Case

In the naive string pattern matching algorithm, what is the worst-case number of character comparisons when searching for a pattern of length m in a text of length n?

A O(n * m)

B O(m^2)

C O(n / m)

D O(n + m)

💡 Hint

Consider that for each position in the text, the algorithm may compare all characters of the pattern.

The naive algorithm checks each position in the text and compares up to m characters, leading to O(n * m) comparisons in the worst case.

🔧 Debug

advanced

Identify the Bug in Naive Pattern Matching Code

What error will the following Java code produce when run, and why?

DSA Java

public class NaiveMatch {
    public static void main(String[] args) {
        String text = "hello";
        String pattern = "lo";
        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(i);
            }
        }
    }
}

A No output; the loop misses the last possible match due to incorrect loop condition

B Prints 2

C Throws StringIndexOutOfBoundsException

D Prints 3

💡 Hint

Check the loop boundary condition for the outer loop.

The outer loop condition uses '<' instead of '<=' which causes it to skip the last valid starting index where the pattern could match.

❓ Predict Output

advanced

Output with Overlapping Patterns

What is the output of this Java code using naive pattern matching when the pattern overlaps in the text?

DSA Java

public class OverlapPattern {
    public static void main(String[] args) {
        String text = "aaaaa";
        String pattern = "aaa";
        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.print(i + " ");
            }
        }
    }
}

A 0 1 2 3

B 0 2

C 1 2 3

D 0 1 2

💡 Hint

Check all starting indices where the pattern "aaa" fully matches, including overlapping ones.

The pattern "aaa" appears starting at indices 0, 1, and 2 in "aaaaa". The code prints all these indices separated by spaces.

🧠 Conceptual

expert

Why is Naive Pattern Matching Inefficient for Certain Texts?

Why does the naive string pattern matching algorithm perform poorly on texts with many repeated characters when searching for certain patterns?

A Because it uses extra memory to store partial matches

B Because it skips some valid matches causing incorrect results

C Because it rechecks characters multiple times leading to many redundant comparisons

D Because it uses hashing which causes collisions

💡 Hint

Think about how the algorithm compares characters when partial matches fail near the start.

The naive algorithm restarts matching at the next position without using information from previous comparisons, causing repeated checks of the same characters especially in repetitive texts.

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