Substring Search Patterns in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Naive Substring Search

What is the output of the following C# code that uses a naive substring search to find all occurrences of a pattern in a text?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static List<int> NaiveSearch(string text, string pattern) {
        List<int> positions = new List<int>();
        int n = text.Length, m = pattern.Length;
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == m)
                positions.Add(i);
        }
        return positions;
    }

    static void Main() {
        string text = "abracadabra";
        string pattern = "abra";
        var result = NaiveSearch(text, pattern);
        Console.WriteLine(string.Join(",", result));
    }
}

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 twice in the text: starting at index 0 and again at index 7. The naive search checks every position and adds the index when a full match is found.

❓ Predict Output

intermediate

Output of KMP Prefix Table Construction

What is the output of the prefix table (also called lps array) constructed by the KMP algorithm for the pattern "ababc"?

DSA C#

using System;

class Program {
    static int[] ComputeLPS(string pattern) {
        int m = pattern.Length;
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    static void Main() {
        string pattern = "ababc";
        var lps = ComputeLPS(pattern);
        Console.WriteLine(string.Join(",", lps));
    }
}

A 1,0,1,2,0

B 0,1,2,0,1

C 0,0,0,1,2

D 0,0,1,2,0

💡 Hint

The lps array stores the length of the longest proper prefix which is also suffix for each prefix of the pattern.

The lps array for "ababc" is [0,0,1,2,0]. This means at index 2, the longest prefix-suffix length is 1 ("a"), at index 3 it is 2 ("ab"), and so on.

🔧 Debug

advanced

Identify the error in Rabin-Karp hash calculation

The following C# code attempts to implement the Rabin-Karp algorithm but produces incorrect results. What is the main error causing the wrong hash values?

DSA C#

using System;

class Program {
    static int ComputeHash(string s, int prime, int mod) {
        int hash = 0;
        for (int i = 0; i < s.Length; i++) {
            hash = (hash * prime + s[i]) % mod;
        }
        return hash;
    }

    static void Main() {
        string text = "hello";
        string pattern = "ell";
        int prime = 101;
        int mod = 1000;
        int patternHash = ComputeHash(pattern, prime, mod);
        int textHash = ComputeHash(text.Substring(0, pattern.Length), prime, mod);
        Console.WriteLine($"Pattern hash: {patternHash}, Text hash: {textHash}");
    }
}

A The rolling hash update is missing for subsequent substrings.

B The character values should be converted to integers differently.

C The modulus value is too small causing frequent collisions.

D The prime number used is not a prime.

💡 Hint

Check how the hash is updated when moving the window over the text.

The code computes the initial hash correctly but does not update the hash efficiently for the next substrings. Rabin-Karp requires a rolling hash update to slide over the text.

❓ Predict Output

advanced

Output of Boyer-Moore Bad Character Table

What is the output of the bad character table for the pattern "example" computed by the Boyer-Moore algorithm?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static Dictionary<char, int> BuildBadCharTable(string pattern) {
        var table = new Dictionary<char, int>();
        int length = pattern.Length;
        for (int i = 0; i < length - 1; i++) {
            table[pattern[i]] = length - 1 - i;
        }
        return table;
    }

    static void Main() {
        string pattern = "example";
        var table = BuildBadCharTable(pattern);
        foreach (var kvp in table) {
            Console.WriteLine($"{kvp.Key}:{kvp.Value}");
        }
    }
}

A

e:0
x:5
a:3
m:2
p:1
l:1

B

e:1
x:5
a:3
m:2
p:1
l:2

C

e:1
x:5
a:3
m:2
p:1
l:1

D

e:1
x:4
a:3
m:2
p:1
l:1

💡 Hint

The bad character table stores the distance from the right end for each character except the last one.

The bad character table for "example" assigns distances from the right end for each character except the last 'e'. For example, 'x' is at index 1, so distance is 6 - 1 = 5.

🧠 Conceptual

expert

Time Complexity Comparison of Substring Search Algorithms

Which of the following statements correctly compares the worst-case time complexities of naive, KMP, and Boyer-Moore substring search algorithms for a text of length n and pattern of length m?

A Naive: O(n), KMP: O(n*m), Boyer-Moore: O(n*m)

B Naive: O(n*m), KMP: O(n), Boyer-Moore: O(n) average but O(n*m) worst-case

C Naive: O(n*m), KMP: O(n*m), Boyer-Moore: O(n)

D Naive: O(n*m), KMP: O(n), Boyer-Moore: O(n*m) average but O(n) worst-case

💡 Hint

Consider how each algorithm processes the text and pattern in worst-case scenarios.

The naive algorithm checks every position and can take O(n*m). KMP preprocesses the pattern and runs in O(n). Boyer-Moore is efficient on average O(n) but can degrade to O(n*m) in worst cases.

Practice

1. What is the main purpose of substring search algorithms in strings?

easy

A. To sort characters in a string alphabetically

B. To find if a smaller string exists inside a larger string

C. To reverse the order of characters in a string

D. To count the total number of characters in a string

Solution

1. Step 1: Understand substring search goal

   Substring search algorithms check if a smaller string (pattern) appears inside a bigger string (text).

2. Step 2: Compare with other options

   Sorting, reversing, and counting characters are different string operations unrelated to substring search.

3. Final Answer:

   To find if a smaller string exists inside a larger string -> Option B

4. Quick Check:

   Substring search = find smaller string inside bigger string [OK]

Hint: Substring search means finding a smaller string inside a bigger one [OK]

Common Mistakes:

• Confusing substring search with sorting or reversing strings
• Thinking substring search counts characters
• Assuming substring search changes the string

2. Which of the following is the correct way to check if string text contains substring pattern in C#?

easy

A. bool found = Contains(text, pattern);

B. bool found = text.Find(pattern);

C. bool found = text.Contains(pattern);

D. bool found = text.Index(pattern);

Solution

1. Step 1: Recall C# string method for substring check

   The correct method to check if a string contains another is Contains, called on the string instance.

2. Step 2: Validate method usage

   text.Contains(pattern) returns a boolean indicating if pattern is inside text. Other options are invalid or do not exist.

3. Final Answer:

   bool found = text.Contains(pattern); -> Option C

4. Quick Check:

   Use Contains method on string to check substring [OK]

Hint: Use text.Contains(pattern) to check substring presence [OK]

Common Mistakes:

• Using non-existent methods like Find or Index
• Calling Contains as a standalone function
• Confusing method names or parameters

3. What will be the output of the following C# code?

string text = "hello world";
string pattern = "wor";
bool result = text.Contains(pattern);
Console.WriteLine(result);

medium

A. True

B. Runtime exception

C. Compilation error

D. False

Solution

1. Step 1: Check if pattern "wor" is in text "hello world"

   The substring "wor" appears starting at index 6 in "hello world".

2. Step 2: Evaluate Contains method result

   Since the substring exists, text.Contains(pattern) returns true, so result is true.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Substring "wor" in "hello world" = true [OK]

Hint: Check if substring is inside text literally to get true/false [OK]

Common Mistakes:

• Assuming Contains returns index instead of bool
• Thinking substring is not present due to partial match
• Confusing output with string printing

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

string text = "data structures";
string pattern = "struct";
int index = text.IndexOf(pattern);
if (index)
{
    Console.WriteLine("Found at " + index);
}

medium

A. The if condition should check if index >= 0

B. IndexOf method does not exist for strings

C. Pattern variable is not declared

D. Console.WriteLine syntax is incorrect

Solution

1. Step 1: Understand IndexOf return value

   IndexOf returns the starting index of the substring or -1 if not found.

2. Step 2: Check if condition usage

   The if condition if (index) is invalid because index is an int, not a boolean. It should check index >= 0 to confirm substring found.

3. Final Answer:

   The if condition should check if index >= 0 -> Option A

4. Quick Check:

   Check index >= 0 to confirm substring found [OK]

Hint: Check if index >= 0 to confirm substring found [OK]

Common Mistakes:

• Using int directly as boolean in if condition
• Assuming IndexOf returns boolean
• Ignoring negative index meaning not found

5. Given a list of strings words and a pattern string p, which approach best finds all words containing p as a substring efficiently in C#?

hard

A. Use words.IndexOf(p) directly

B. Sort the list and use binary search for the pattern

C. Replace all occurrences of p in each word with empty string

D. Use a loop to check each word with word.Contains(p) and collect matches

Solution

1. Step 1: Understand substring search in multiple strings

   To find all words containing p, we must check each word individually for the substring.

2. Step 2: Evaluate options for efficiency and correctness

   Using a loop with word.Contains(p) is straightforward and efficient. Sorting and binary search do not help substring search. words.IndexOf(p) is invalid because words is a list of strings, not a string. Replacing substrings does not find matches.

3. Final Answer:

   Use a loop to check each word with word.Contains(p) and collect matches -> Option D

4. Quick Check:

   Loop + Contains per word finds all substring matches [OK]

Hint: Loop through words and use Contains to find substring matches [OK]

Common Mistakes:

• Trying binary search for substring matching
• Using IndexOf on list instead of strings
• Replacing substrings instead of checking presence