String Pattern Matching Naive in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the length of the pattern string.

DSA Java

int m = pattern.[1]();

Drag options to blanks, or click blank then click option'

Alength

Bsize

CgetLength

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using size() which is for collections, not strings.

Using getLength() which does not exist for strings.

The length() method returns the number of characters in a string in Java.

2fill in blank

medium

Complete the code to check if the substring of text matches the pattern.

DSA Java

if (text.substring(i, i + m).[1](pattern)) {

Drag options to blanks, or click blank then click option'

AcompareTo

BequalsIgnoreCase

Cequals

Dcontains

Attempts:

3 left

💡 Hint

Common Mistakes

Using contains() which checks if pattern is anywhere inside, not exact match.

Using equalsIgnoreCase() which ignores case differences.

equals() checks if two strings have exactly the same characters in the same order.

3fill in blank

hard

Fix the error in the loop condition to avoid index out of bounds.

DSA Java

for (int i = 0; i <= text.length() - [1]; i++) {

Drag options to blanks, or click blank then click option'

Apattern.length() + 1

Bpattern.length()

Cpattern.length() - 1

Dpattern.length() * 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using pattern.length() + 1 causes missing last possible match.

Using pattern.length() - 1 causes substring to go beyond text length.

We stop at text length minus pattern length to avoid substring going out of bounds.

4fill in blank

hard

Fill both blanks to correctly count pattern matches in the text.

DSA Java

int count = 0;
for (int i = 0; i <= text.length() - [1]; i++) {
    if (text.substring(i, i + [2]).equals(pattern)) {
        count++;
    }
}

Drag options to blanks, or click blank then click option'

Apattern.length()

Btext.length()

Cpattern.length() - 1

Dtext.length() - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using text.length() in substring causes errors.

Using pattern.length() - 1 misses last character.

Both blanks must be pattern.length() to correctly check substrings of the pattern's length.

5fill in blank

hard

Fill all three blanks to return the first index of pattern in text or -1 if not found.

DSA Java

for (int i = 0; i <= text.length() - [1]; i++) {
    if (text.substring(i, i + [2]).equals([3])) {
        return i;
    }
}
return -1;

Drag options to blanks, or click blank then click option'

Apattern.length()

Btext.length()

Cpattern

Dtext

Attempts:

3 left

💡 Hint

Common Mistakes

Using text.length() in substring or loop causes errors.

Comparing substring to text instead of pattern.

We use pattern.length() for loop limit and substring length, and compare substring to pattern.

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