String Pattern Matching Naive in DSA Java - Build from Scratch

String Pattern Matching Naive

📖 Scenario: You are building a simple text search tool. You want to find if a small word (pattern) appears inside a bigger text (string).This is like looking for a word in a book by checking each letter one by one.

🎯 Goal: Build a program that checks if a pattern exists in a text using the naive string matching method.You will write code to slide the pattern over the text and compare characters one by one.

📋 What You'll Learn

Create a String variable called text with the exact value "hello world".

Create a String variable called pattern with the exact value "world".

Write a for loop with variable i to slide over text from 0 to text.length() - pattern.length().

Inside the loop, use a boolean variable found set to true before checking characters.

Use a nested for loop with variable j to compare characters of pattern and text starting at i.

If any character does not match, set found to false and break the inner loop.

If found remains true after inner loop, print "Pattern found at index " + i and break the outer loop.

If the pattern is not found after the loop, print "Pattern not found".

💡 Why This Matters

🌍 Real World

Searching for words or phrases inside documents, messages, or logs is a common task in text editors, search engines, and data analysis.

💼 Career

Understanding basic string matching helps in roles like software development, data processing, and quality assurance where text processing is frequent.

1

Create the text string

Create a String variable called text and set it to "hello world".

DSA Java

# Your code here
// Create the text string

Hint

Use String text = "hello world"; to create the text.

2

Create the pattern string

Create a String variable called pattern and set it to "world".

DSA Java

public class Main {
    public static void main(String[] args) {
        String text = "hello world";
        // Your code here
        // Create the pattern string
    }
}

Hint

Use String pattern = "world"; to create the pattern.

3

Write the naive pattern matching loops

Write a for loop with variable i from 0 to text.length() - pattern.length(). Inside it, create a boolean variable found set to true. Then write a nested for loop with variable j from 0 to pattern.length() to compare pattern.charAt(j) with text.charAt(i + j). If they differ, set found to false and break the inner loop.

DSA Java

public class Main {
    public static void main(String[] args) {
        String text = "hello world";
        String pattern = "world";
        // Your code here
        // Write the naive pattern matching loops
    }
}

Hint

Use two nested for loops and a boolean found to check each position.

4

Print the result of pattern matching

Inside the outer for loop, after the inner loop, if found is true, print "Pattern found at index " + i and break the outer loop. After the loop, if the pattern was not found, print "Pattern not found".

DSA Java

public class Main {
    public static void main(String[] args) {
        String text = "hello world";
        String pattern = "world";
        // Your code here
        // Print the result of pattern matching
    }
}

Hint

Use System.out.println to print the result and a boolean foundPattern to track if found.

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