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 code that searches for the pattern "ana" in the text "banana" using a naive substring search?

DSA C

const char* text = "banana";
const char* pattern = "ana";

for (int i = 0; text[i] != '\0'; i++) {
    int j = 0;
    while (pattern[j] != '\0' && text[i + j] == pattern[j]) {
        j++;
    }
    if (pattern[j] == '\0') {
        printf("%d ", i);
    }
}
printf("\n");

A 0 2

B 1 2 3

C 2 4

D 1 3

💡 Hint

Check each position in the text where the pattern matches fully.

The pattern "ana" appears starting at index 1 ("banana") and index 3 ("banana"). So the output prints "1 3 ".

❓ Predict Output

intermediate

Output of KMP Prefix Table Construction

What is the output array (prefix table) constructed by the KMP algorithm for the pattern "ABABAC"?

DSA C

int prefix[] = {0, 0, 0, 0, 0, 0};
char pattern[] = "ABABAC";
int len = 0;
for (int i = 1; pattern[i] != '\0'; i++) {
    while (len > 0 && pattern[i] != pattern[len]) {
        len = prefix[len - 1];
    }
    if (pattern[i] == pattern[len]) {
        len++;
        prefix[i] = len;
    }
}
for (int i = 0; i < 6; i++) {
    printf("%d ", prefix[i]);
}
printf("\n");

A 0 0 1 2 3 1

B 0 1 0 1 2 0

C 0 0 1 2 3 0

D 0 0 1 2 0 1

💡 Hint

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

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

🔧 Debug

advanced

Identify the error in Rabin-Karp hash update

What error will occur when running this Rabin-Karp rolling hash update code snippet for substring search?

DSA C

int base = 256;
int prime = 101;
int h = 1;
int pattern_len = 3;
for (int i = 0; i < pattern_len - 1; i++) {
    h = (h * base) % prime;
}
int text_hash = 0;
int pattern_hash = 0;
char text[] = "abcd";
char pattern[] = "bcd";
for (int i = 0; i < pattern_len; i++) {
    pattern_hash = (base * pattern_hash + pattern[i]) % prime;
    text_hash = (base * text_hash + text[i]) % prime;
}
// Update hash for next window
text_hash = (base * (text_hash - text[0] * h) + text[pattern_len]) % prime;
if (text_hash < 0) text_hash += prime;
printf("%d\n", text_hash);

A Runtime error: array index out of bounds

B No error, prints 31

C Wrong hash value due to missing parentheses

D Negative hash value without correction

💡 Hint

Check the calculation of the rolling hash and the array indices used.

The code correctly computes the rolling hash and adjusts negative values. The output is 31, no runtime error occurs.

❓ Predict Output

advanced

Output of Boyer-Moore Bad Character Table

What is the value of bad character table entry for character 'c' in the pattern "abcabc" using Boyer-Moore preprocessing?

DSA C

int badChar[256];
char pattern[] = "abcabc";
int m = 6;
for (int i = 0; i < 256; i++) {
    badChar[i] = -1;
}
for (int i = 0; i < m; i++) {
    badChar[(unsigned char)pattern[i]] = i;
}
printf("%d\n", badChar['c']);

A 5

B 2

C -1

D 3

💡 Hint

The bad character table stores the last occurrence index of each character in the pattern.

The character 'c' appears at indices 2 and 5. The table stores the last occurrence, which is 5.

🧠 Conceptual

expert

Minimum number of comparisons in substring search

Which substring search algorithm guarantees the minimum worst-case number of character comparisons for searching a pattern of length m in a text of length n?

A Knuth-Morris-Pratt (KMP) algorithm

B Naive substring search algorithm

C Rabin-Karp algorithm

D Boyer-Moore algorithm

💡 Hint

Consider worst-case linear time complexity and character comparisons.

KMP guarantees O(n) worst-case comparisons by using prefix table to avoid re-examining characters.