String Pattern Matching Naive in DSA Java - Execution Trace

Concept Flow - String Pattern Matching Naive

Start at text index i=0

↓

Compare pattern with text from i

↓

All chars match?

No→i = i + 1

↓

Reached end of text?

Yes→Stop

↓

Pattern found

Start matching pattern at each position in text. If all characters match, pattern found. Else move to next position until end.

Execution Sample

DSA Java

String text = "ababcabc";
String pattern = "abc";
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);
}

Check each position in text to see if pattern matches starting there.

Execution Table

Step	Operation	Text Index i	Pattern Index j	Match Check	Action	Visual State
1	Start outer loop	0	-	-	Check pattern at i=0	Text: ababcabc Pattern: abc
2	Compare chars	0	0	a == a (match)	Continue	i=0, j=0
3	Compare chars	0	1	b == b (match)	Continue	i=0, j=1
4	Compare chars	0	2	a != c (mismatch)	Break inner loop	i=0, j=2
5	Increment i	1	-	-	Move to i=1	i=1
6	Compare chars	1	0	b != a (mismatch)	Break inner loop	i=1, j=0
7	Increment i	2	-	-	Move to i=2	i=2
8	Compare chars	2	0	a == a (match)	Continue	i=2, j=0
9	Compare chars	2	1	b == b (match)	Continue	i=2, j=1
10	Compare chars	2	2	c == c (match)	Pattern found	Pattern found at index 2
11	Increment i	3	-	-	Move to i=3	i=3
12	Compare chars	3	0	b != a (mismatch)	Break inner loop	i=3, j=0
13	Increment i	4	-	-	Move to i=4	i=4
14	Compare chars	4	0	c != a (mismatch)	Break inner loop	i=4, j=0
15	Increment i	5	-	-	Move to i=5	i=5
16	Compare chars	5	0	a == a (match)	Continue	i=5, j=0
17	Compare chars	5	1	b == b (match)	Continue	i=5, j=1
18	Compare chars	5	2	c == c (match)	Pattern found	Pattern found at index 5
19	Increment i	6	-	-	Move to i=6	i=6
20	End	-	-	-	i=6 exceeds limit, stop	Search complete

💡 i reached 6 which is text length - pattern length + 1, no more positions to check

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 11	After Step 13	After Step 15	After Step 19	Final
i	0	1	2	3	4	5	6	6
j	-	0	0	0	0	0	0	-

Key Moments - 3 Insights

Why do we break the inner loop when a mismatch is found?

Because continuing to check further characters won't match if one character differs, as shown in steps 4 and 6 where mismatch breaks inner loop early.

Why does the outer loop stop at i = text.length - pattern.length?

Because starting beyond that index would mean pattern can't fit fully in text, as shown in step 20 where i=6 stops the search.

How do we know when the pattern is found?

When inner loop index j reaches pattern length, meaning all characters matched, as in steps 10 and 18.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of j at step 4?

A 2

B 1

C 0

D -

💡 Hint

Check the 'Pattern Index j' column at step 4 in the execution table.

At which step does the pattern first get found in the text?

A Step 10

B Step 16

C Step 4

D Step 21

💡 Hint

Look for 'Pattern found' in the 'Action' column in the execution table.

If the pattern length was 2 instead of 3, at which step would the outer loop stop?

A Step 21

B Step 19

C Step 17

D Step 13

💡 Hint

Outer loop stops when i > text.length - pattern.length; check variable_tracker for i values.

Concept Snapshot

Naive String Pattern Matching:
- Check pattern at each text index i
- Compare characters one by one
- If mismatch, move i by 1
- If all match, pattern found at i
- Stop when i > text length - pattern length

Full Transcript

This visualization shows how naive string pattern matching works by checking the pattern at every possible position in the text. We start with i=0 and compare each character of the pattern with the text. If all characters match, we find the pattern at that index. If a mismatch occurs, we break the inner loop and move i forward by one. The process repeats until i reaches the last possible starting position where the pattern can fit. The execution table tracks each comparison and action step by step, showing when matches and mismatches happen. The variable tracker shows how the indices i and j change over time. Key moments clarify why we break early on mismatch, why the outer loop stops at a certain point, and how we detect a full match. The quiz tests understanding of these steps by referencing the execution table and variable changes.

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