Substring Search Patterns in DSA Java

Mental Model

Find if a smaller word appears inside a bigger word by checking each position one by one.

Analogy: Like looking for a small sticker hidden inside a big book page by flipping through each spot carefully.

Text: H E L L O   W O R L D
Pattern:   W O R
Positions: 0 1 2 3 4 5 6 7 8 9 10
             ↑

Dry Run Walkthrough

Input: text: HELLO WORLD, pattern: WOR

Goal: Find the starting position where 'WOR' appears in 'HELLO WORLD'

Step 1: Check substring starting at index 0: HEL

HELLO WORLD
Pattern: WOR
Check at index 0: HEL vs WOR

Why: Start checking from the beginning of the text

Step 2: Check substring starting at index 1: ELL

HELLO WORLD
Pattern: WOR
Check at index 1: ELL vs WOR

Why: Move one step forward to check next possible match

Step 3: Check substring starting at index 2: LLO

HELLO WORLD
Pattern: WOR
Check at index 2: LLO vs WOR

Why: Continue checking next position

Step 4: Check substring starting at index 3: LO

HELLO WORLD
Pattern: WOR
Check at index 3: LO  vs WOR

Why: Keep moving forward to find pattern

Step 5: Check substring starting at index 4: O W

HELLO WORLD
Pattern: WOR
Check at index 4: O W vs WOR

Why: Check next possible start

Step 6: Check substring starting at index 5: WO

HELLO WORLD
Pattern: WOR
Check at index 5:  WO vs WOR

Why: Check next possible start

Step 7: Check substring starting at index 6: WOR

HELLO WORLD
Pattern: WOR
Check at index 6: WOR vs WOR

Why: Found substring matching pattern

Result:

HELLO WORLD
Pattern: WOR
Match found at index 6

Annotated Code

DSA Java

public class SubstringSearch {
    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break; // mismatch found, stop checking this position
                }
            }
            if (j == m) {
                return i; // full match found starting at i
            }
        }
        return -1; // no match found
    }

    public static void main(String[] args) {
        String text = "HELLO WORLD";
        String pattern = "WOR";
        int index = search(text, pattern);
        if (index != -1) {
            System.out.println("Match found at index " + index);
        } else {
            System.out.println("No match found");
        }
    }
}

for (int i = 0; i <= n - m; i++) {

slide the pattern start position through the text

for (j = 0; j < m; j++) {

check each character of the pattern against text

if (text.charAt(i + j) != pattern.charAt(j)) { break; }

stop checking this position if characters don't match

if (j == m) { return i; }

if full pattern matched, return start index

Output

Match found at index 6

Complexity Analysis

Time: O(n*m) because for each of the n-m+1 positions, we compare up to m characters

Space: O(1) because no extra space is used except variables

vs Alternative: Naive search is simple but slow; advanced algorithms like KMP improve to O(n) by avoiding repeated checks

Edge Cases

Empty pattern

Returns 0 because empty pattern matches at start

DSA Java

for (int i = 0; i <= n - m; i++) {

Pattern longer than text

Returns -1 immediately because no match possible

DSA Java

for (int i = 0; i <= n - m; i++) {

Pattern not found in text

Returns -1 after checking all positions

DSA Java

return -1; // no match found

When to Use This Pattern

When you need to find if a small word appears inside a big word, use substring search by checking each position for a match.

Common Mistakes

Mistake: Checking beyond text length causing index errors
Fix: Limit loop to i <= n - m to avoid out-of-bound checks

Mistake: Not breaking inner loop on mismatch causing unnecessary checks
Fix: Break inner loop immediately when characters don't match

Summary

It finds if and where a smaller string appears inside a bigger string by checking each possible position.

Use it when you want to locate a pattern inside a text simply and clearly.

The key insight is to slide the pattern over the text and compare characters one by one until a match is found.

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