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.