Substring Search Patterns in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Substring Search

What is the output of the following Java code that searches for a pattern in a text using the naive substring search method?

DSA Java

public class NaiveSearch {
    public static void main(String[] args) {
        String text = "abracadabra";
        String pattern = "abra";
        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.print(i + " ");
            }
        }
    }
}

A 0 7

B 0 3 7

C 3 7

D 7

💡 Hint

Check where the pattern "abra" fully matches in the text "abracadabra".

The pattern "abra" appears at index 0 and again at index 7 in the text. The naive search prints these starting indices.

❓ Predict Output

intermediate

Output of KMP Prefix Table Construction

What is the output of the following Java code that builds the prefix table (lps array) for the pattern "ABABAC" using the KMP algorithm?

DSA Java

public class KMPPrefix {
    public static void main(String[] args) {
        String pattern = "ABABAC";
        int[] lps = new int[pattern.length()];
        int len = 0;
        int i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        for (int val : lps) {
            System.out.print(val + " ");
        }
    }
}

A 0 0 1 2 3 0

B 0 1 0 1 2 0

C 0 0 1 2 0 1

D 0 1 2 3 4 0

💡 Hint

The prefix table stores lengths of longest proper prefix which is also suffix for each prefix of the pattern.

For pattern "ABABAC", the lps array is [0,0,1,2,3,0]. This means at index 4, the longest prefix-suffix length is 3, and at index 5 it resets to 0.

🔧 Debug

advanced

Identify the Error in Rabin-Karp Hash Calculation

Consider the following Java code snippet for Rabin-Karp substring search. What error will it cause when run?

DSA Java

public class RabinKarp {
    public static void main(String[] args) {
        String text = "hellohello";
        String pattern = "hello";
        int prime = 101;
        int patternHash = 0, textHash = 0;
        int m = pattern.length();
        int h = 1;
        for (int i = 0; i < m - 1; i++) {
            h = (h * 256) % prime;
        }
        for (int i = 0; i < m; i++) {
            patternHash = (256 * patternHash + pattern.charAt(i)) % prime;
            textHash = (256 * textHash + text.charAt(i)) % prime;
        }
        for (int i = 0; i <= text.length() - m; i++) {
            if (patternHash == textHash) {
                int j;
                for (j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        break;
                    }
                }
                if (j == m) {
                    System.out.print(i + " ");
                }
            }
            if (i < text.length() - m) {
                textHash = (256 * (textHash - text.charAt(i) * h) + text.charAt(i + m)) % prime;
                if (textHash < 0) {
                    textHash += prime;
                }
            }
        }
    }
}

A Syntax error: missing semicolon in line 15

B Runtime error due to negative hash values not handled

C Logical error: hash calculation uses wrong base value

D No error; prints "0 5 "

💡 Hint

Check how negative hash values are handled after rolling hash update.

The code correctly handles negative hash values by adding prime if textHash < 0. It prints indices 0 and 5 where pattern matches.

❓ Predict Output

advanced

Output of Z-Algorithm for Pattern Matching

What is the output of the following Java code that computes the Z-array for the string "aabcaabxaaaz"?

DSA Java

public class ZAlgorithm {
    public static void main(String[] args) {
        String s = "aabcaabxaaaz";
        int n = s.length();
        int[] Z = new int[n];
        int L = 0, R = 0;
        for (int i = 1; i < n; i++) {
            if (i > R) {
                L = R = i;
                while (R < n && s.charAt(R - L) == s.charAt(R)) {
                    R++;
                }
                Z[i] = R - L;
                R--;
            } else {
                int k = i - L;
                if (Z[k] < R - i + 1) {
                    Z[i] = Z[k];
                } else {
                    L = i;
                    while (R < n && s.charAt(R - L) == s.charAt(R)) {
                        R++;
                    }
                    Z[i] = R - L;
                    R--;
                }
            }
        }
        for (int val : Z) {
            System.out.print(val + " ");
        }
    }
}

A 0 1 0 0 3 1 0 0 2 1 1 0

B 0 1 0 0 4 1 0 0 3 1 1 0

C 0 2 0 0 3 1 0 0 2 1 1 0

D 0 2 0 0 3 1 0 0 2 1 0 0

💡 Hint

Z-array at position i shows length of substring starting at i matching prefix.

The Z-array for "aabcaabxaaaz" is [0,2,0,0,3,1,0,0,2,1,1,0]. This matches the longest prefix matches at each position.

🧠 Conceptual

expert

Time Complexity Comparison of Substring Search Algorithms

Which of the following statements correctly compares the worst-case time complexities of naive substring search, KMP algorithm, and Rabin-Karp algorithm for searching a pattern of length m in a text of length n?

A Naive: O(n*m), KMP: O(n*m), Rabin-Karp: O(n)

B Naive: O(n*m), KMP: O(n), Rabin-Karp: O(n*m) worst-case

C Naive: O(n), KMP: O(n*m), Rabin-Karp: O(n)

D Naive: O(n), KMP: O(n), Rabin-Karp: O(n*m)

💡 Hint

Consider how each algorithm handles pattern matching and worst-case scenarios.

Naive search checks every position leading to O(n*m). KMP preprocesses pattern for O(n) search. Rabin-Karp average O(n+m), but worst-case hash collisions cause O(n*m).

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