Substring Search Patterns in DSA Java - Execution Trace

Concept Flow - Substring Search Patterns

Start at index 0 in text

↓

Compare substring chars with text chars

↓

All chars match?

No→Move to next index in text

↓

Reached end of text?

Yes→Stop

↓

Return match index

Start checking from the first character of the text. Compare substring characters one by one. If all match, return the index. If not, move to the next index and repeat until the end.

Execution Sample

DSA Java

String text = "hello world";
String pattern = "lo";
for (int i = 0; i <= text.length() - pattern.length(); i++) {
  if (text.substring(i, i + pattern.length()).equals(pattern)) {
    System.out.println(i);
  }
}

This code searches for the substring "lo" in "hello world" and prints the starting index of each match.

Execution Table

Step	Operation	Current Index (i)	Substring Compared	Match?	Action	Visual State
1	Check substring at index 0	0	"he"	No	Move to next index	hello world
2	Check substring at index 1	1	"el"	No	Move to next index	hello world
3	Check substring at index 2	2	"ll"	No	Move to next index	hello world
4	Check substring at index 3	3	"lo"	Yes	Print index 3	hello world
5	Check substring at index 4	4	"o "	No	Move to next index	hello world
6	Check substring at index 5	5	" w"	No	Move to next index	hello world
7	Check substring at index 6	6	"wo"	No	Move to next index	hello world
8	Check substring at index 7	7	"or"	No	Move to next index	hello world
9	Check substring at index 8	8	"rl"	No	Move to next index	hello world
10	Check substring at index 9	9	"ld"	No	Reached end, stop	hello world

💡 Reached end of text where substring cannot fit, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
i	0	1	2	3	4	5	6	7	8	9	10
substring compared	"he"	"el"	"ll"	"lo"	"o "	" w"	"wo"	"or"	"rl"	"ld"	N/A
match found	No	No	No	Yes	No	No	No	No	No	No	N/A

Key Moments - 3 Insights

Why do we stop checking when i reaches text.length() - pattern.length()?

Because beyond this point, the substring would not fit inside the remaining text. See execution_table row 10 where index 9 is last checked.

Why do we compare substring of length equal to pattern length at each step?

To ensure we check exactly the same length as the pattern for a match. See execution_table column 'Substring Compared' for each step.

What happens if the substring matches at multiple places?

The code prints each starting index where a match occurs. In this example, only index 3 matches as shown in step 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the substring compared at step 5?

A "o "

B "lo"

C "el"

D "wo"

💡 Hint

Check the 'Substring Compared' column at row with Step 5.

At which step does the substring match the pattern?

A Step 6

B Step 2

C Step 4

D Step 9

💡 Hint

Look for 'Match?' column with 'Yes' in execution_table.

If the pattern was "ll", at which step would the match occur?

A Step 4

B Step 3

C Step 2

D Step 1

💡 Hint

Check the substring compared at step 3 in execution_table.

Concept Snapshot

Substring Search Pattern:
- Start from index 0 in text
- Compare substring of pattern length
- If match, return index
- Else move to next index
- Stop when substring can't fit
- Prints all match start indices

Full Transcript

This visualization shows how substring search works by checking each possible position in the text for the pattern. We start at index 0 and compare the substring of the same length as the pattern. If all characters match, we print the index. If not, we move to the next index and repeat. We stop when the remaining text is shorter than the pattern. The example searches for "lo" in "hello world" and finds a match at index 3.

Practice

1. What does the indexOf method in Java's String class return when searching for a substring that exists in the string?

easy

A. The starting index of the first occurrence of the substring

B. The length of the substring

C. The number of times the substring appears

D. A boolean indicating if the substring exists

Solution

1. Step 1: Understand the purpose of indexOf

   The indexOf method searches for the first occurrence of a substring inside a string and returns its position.

2. Step 2: Identify the return value when substring exists

   If the substring is found, indexOf returns the starting index (0-based) of that substring in the string.

3. Final Answer:

   The starting index of the first occurrence of the substring -> Option A

4. Quick Check:

   indexOf returns index, not count or boolean [OK]

Hint: Remember: indexOf returns position, not count or boolean [OK]

Common Mistakes:

• Thinking indexOf returns count of occurrences
• Assuming it returns true/false
• Confusing indexOf with substring length

2. Which of the following is the correct syntax to find the first occurrence of substring "cat" in string str in Java?

easy

A. int pos = str.find("cat");

B. int pos = str.search("cat");

C. int pos = str.indexOf("cat");

D. int pos = str.contains("cat");

Solution

1. Step 1: Recall Java String methods for substring search

   Java's String class uses indexOf to find substring positions.

2. Step 2: Check method names and return types

   find and search are not valid String methods; contains returns boolean, not int.

3. Final Answer:

   int pos = str.indexOf("cat"); -> Option C

4. Quick Check:

   Use indexOf for substring position [OK]

Hint: Use indexOf for position, contains for boolean check [OK]

Common Mistakes:

• Using non-existent methods like find or search
• Using contains which returns boolean, not index
• Confusing method names from other languages

3. What is the output of the following Java code?

String text = "hello world";
int pos = text.indexOf("lo");
System.out.println(pos);

medium

A. -1

B. 3

C. 4

D. 5

Solution

1. Step 1: Locate substring "lo" in "hello world"

   Counting indices: h(0), e(1), l(2), l(3), o(4). The substring "lo" starts at index 3 (l at 3, o at 4).

2. Step 2: Understand indexOf return value

   indexOf returns the starting index of the substring, which is 3 here.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Substring "lo" starts at index 3 [OK]

Hint: Count string indices from 0 to find substring start [OK]

Common Mistakes:

• Counting from 1 instead of 0
• Returning index of second character in substring
• Assuming -1 means substring found

4. Identify the error in the following Java code snippet for substring search:

String s = "banana";
int index = s.indexOf('an');
System.out.println(index);

medium

A. Using single quotes for substring instead of double quotes

B. Missing semicolon after indexOf call

C. indexOf method does not exist for String

D. Printing index before assignment

Solution

1. Step 1: Check substring argument type in indexOf

   The indexOf method expects a String argument, but single quotes denote a char.

2. Step 2: Identify correct syntax for substring

   Substring literals must be in double quotes, so 'an' should be "an".

3. Final Answer:

   Using single quotes for substring instead of double quotes -> Option A

4. Quick Check:

   Substring literals need double quotes [OK]

Hint: Use double quotes for substrings, single for chars [OK]

Common Mistakes:

• Using single quotes for multi-character substrings
• Confusing char and String types
• Ignoring compiler error messages

5. Given a string text, which code snippet correctly finds all starting indices of substring "ab" in text using indexOf?

hard

A. int index = 0;
while (index < text.length()) {
index = text.indexOf("ab");
System.out.print(index + " ");
index++;
}

B. for (int i = 0; i < text.length(); i++) {
if (text.indexOf("ab") == i) System.out.print(i + " ");
}

C. int index = text.indexOf("ab");
while (index != -1) {
System.out.print(index + " ");
index = text.indexOf("ab");
}

D. int index = 0;
while ((index = text.indexOf("ab", index)) != -1) {
System.out.print(index + " ");
index++;
}

Solution

1. Step 1: Understand how to find multiple occurrences with indexOf

   Use indexOf(substring, fromIndex) to search from a moving start index to find all occurrences.

2. Step 2: Analyze each option's logic

   int index = 0; while ((index = text.indexOf("ab", index)) != -1) { System.out.print(index + " "); index++; } correctly updates index after each found occurrence to avoid infinite loop and find all positions. Others either do not update index properly or repeatedly search from start.

3. Final Answer:

   int index = 0; while ((index = text.indexOf("ab", index)) != -1) { System.out.print(index + " "); index++; } -> Option D

4. Quick Check:

   Use indexOf with start index and increment after each find [OK]

Hint: Increment start index after each found substring to continue search [OK]

Common Mistakes:

• Not updating start index causing infinite loop
• Always searching from start index 0
• Confusing indexOf usage with for-loop index