Substring Search Patterns in DSA C - Execution Trace

Concept Flow - Substring Search Patterns

Start at index 0 in text

↓

Compare substring with text segment

↓

Substring found

↓

Repeat until end of text - substring length

↓

Done

The search starts at the beginning of the text and compares the substring with each segment. If it matches, we stop; if not, we move one step forward and repeat until the end.

Execution Sample

DSA C

int substring_search(char *text, char *pattern) {
  int n = strlen(text);
  int m = strlen(pattern);
  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) return i;
  }
  return -1;
}

This code searches for the first occurrence of 'pattern' in 'text' by checking each possible position.

Execution Table

Step	Operation	Index i	Index j	Characters Compared	Match So Far	Action	Result
1	Start outer loop	0	-	-	-	Check substring at text[0..2]	Continue
2	Compare characters	0	0	text[0]='a' vs pattern[0]='a'	Match	Continue inner loop	Continue
3	Compare characters	0	1	text[1]='b' vs pattern[1]='b'	Match	Continue inner loop	Continue
4	Compare characters	0	2	text[2]='c' vs pattern[2]='c'	Match	Inner loop complete	Substring found
5	Return index	0	-	-	-	Return 0	0

💡 Substring found at index 0, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	-	0	0	0	0	0
j	-	-	0	1	2	3
Match So Far	-	-	Yes	Yes	Yes	Yes

Key Moments - 3 Insights

Why do we stop checking characters when a mismatch is found?

Because if any character does not match, the substring cannot be at that position. This is shown in step 2 and 3 where comparison continues only if characters match.

Why does the outer loop run only until n - m?

Because the substring cannot fit beyond index n - m in the text. This prevents out-of-bound errors and is why the loop stops at step 1.

What does it mean when j equals m?

It means all characters of the substring matched the text segment, so the substring is found. This is shown in step 4 where j reaches 3 (length of pattern).

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'j' at step 3?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Index j' column at step 3 in the execution_table.

At which step does the substring search confirm a full match?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for the step where 'Inner loop complete' and 'Substring found' appear in the Action and Result columns.

If the substring was not found at index 0, what would happen next in the execution table?

A Return index 0 immediately

B Increment i to 1 and start comparing again

C Stop the search and return -1

D Increment j beyond substring length

💡 Hint

Refer to the concept_flow where after a mismatch, the search moves to the next index.

Concept Snapshot

Substring Search Patterns:
- Start at index 0 in text
- Compare substring characters one by one
- If mismatch, move to next index
- If all match, return index
- Stop when index > text length - substring length

Full Transcript

This visualization shows how substring search works by checking each possible position in the text. We start at index 0 and compare each character of the substring with the text. If all characters match, we return the current index. If a mismatch occurs, we move to the next index and repeat. The search stops when the substring is found or when no more positions can fit the substring. Variables i and j track the current position in text and substring respectively. The execution table traces each comparison step, showing how the search progresses.

Practice

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

easy

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

B. To sort the characters of a string alphabetically

C. To reverse the entire string

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

Solution

1. Step 1: Understand substring search purpose

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

2. Step 2: Compare options with definition

   Only To find if a smaller string exists inside a larger string describes finding a smaller string inside a larger one, which matches substring search.

3. Final Answer:

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

4. Quick Check:

   Substring search = find smaller string inside larger [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
• Mixing substring search with string length calculation

2. Which of the following is the correct syntax to check if string pattern is a substring of string text in C?

easy

A. if (text.find(pattern)) { /* found */ }

B. if (text.contains(pattern)) { /* found */ }

C. if (pattern in text) { /* found */ }

D. if (strstr(text, pattern) != NULL) { /* found */ }

Solution

1. Step 1: Recall C substring search function

   In C, strstr() returns a pointer to the first occurrence of pattern in text, or NULL if not found.

2. Step 2: Check each option's syntax

   if (strstr(text, pattern) != NULL) { /* found */ } uses strstr correctly with NULL check. Options A, B, C use syntax from other languages or invalid in C.

3. Final Answer:

   if (strstr(text, pattern) != NULL) { /* found */ } -> Option D

4. Quick Check:

   C substring search uses strstr() [OK]

Hint: Use strstr() in C to find substring, check for NULL [OK]

Common Mistakes:

• Using methods from other languages like contains() or find()
• Not checking if strstr() returns NULL
• Confusing order of arguments in strstr()

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

char text[] = "hello world";
char *pos = strstr(text, "wor");
if (pos != NULL) {
    printf("%ld", pos - text);
} else {
    printf("-1");
}

medium

A. 6

B. 0

C. -1

D. 3

Solution

1. Step 1: Understand strstr() return value

   strstr(text, "wor") returns pointer to first occurrence of "wor" in "hello world", which starts at index 6.

2. Step 2: Calculate pointer difference

   Subtracting text pointer from pos gives index 6, which is printed.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Substring "wor" starts at index 6 [OK]

Hint: Pointer difference in strstr() gives substring start index [OK]

Common Mistakes:

• Printing pointer value instead of index difference
• Assuming substring starts at 0 or 3 incorrectly
• Not checking if strstr() returns NULL before subtracting

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

char *find_substring(char *text, char *pattern) {
    for (int i = 0; i <= strlen(text); i++) {
        if (strncmp(&text[i], pattern, strlen(pattern)) == 0) {
            return &text[i];
        }
    }
    return NULL;
}

medium

A. Function should return int index, not pointer

B. strncmp() is used incorrectly; should use strcmp() instead

C. The loop condition should be 'i < strlen(text) - strlen(pattern) + 1' to avoid overflow

D. No error; code works correctly

Solution

1. Step 1: Analyze loop boundary

   The loop runs from 0 to strlen(text), but comparing substrings beyond text length minus pattern length causes overflow.

2. Step 2: Correct loop condition

   Loop should run until i <= strlen(text) - strlen(pattern) to safely compare substrings of pattern length.

3. Final Answer:

   The loop condition should be 'i < strlen(text) - strlen(pattern) + 1' to avoid overflow -> Option C

4. Quick Check:

   Loop boundary must prevent substring overflow [OK]

Hint: Loop till text length minus pattern length to avoid overflow [OK]

Common Mistakes:

• Looping beyond valid substring start positions
• Using strcmp instead of strncmp for partial comparison
• Ignoring return type correctness

5. You want to find all occurrences of substring pat in string txt using C. Which approach correctly finds all start indices of pat in txt?

hard

A. Use strstr() once and return the first found position only

B. Use a loop with strstr() starting from last found position + 1 until strstr() returns NULL

C. Use strcmp() on entire text and pattern directly

D. Use strlen() to compare lengths and decide if substring exists

Solution

1. Step 1: Understand strstr() usage for multiple occurrences

   strstr() returns pointer to first occurrence. To find all, repeatedly call strstr() starting after last found position.

2. Step 2: Evaluate options

   Use a loop with strstr() starting from last found position + 1 until strstr() returns NULL correctly describes looping with strstr() advancing pointer. Use strstr() once and return the first found position only finds only first occurrence. Options C and D do not find all occurrences.

3. Final Answer:

   Use a loop with strstr() starting from last found position + 1 until strstr() returns NULL -> Option B

4. Quick Check:

   Loop with strstr() to find all occurrences [OK]

Hint: Loop with strstr() advancing pointer to find all matches [OK]

Common Mistakes:

• Using strstr() only once for all matches
• Using strcmp() which compares whole strings only
• Relying on length checks without searching