Find the Index of the First Occurrence in a String - C Solution

1. Introduction

In this blog post, we'll tackle a common string manipulation problem in C programming: finding the first occurrence of a substring (needle) within another string (haystack). This problem is fundamental in text processing and forms the basis for more complex text algorithms.

Problem

The challenge is to find the index of the first occurrence of a given substring 'needle' in another string 'haystack'. If 'needle' is not part of 'haystack', the function should return -1. This problem tests our ability to manipulate and traverse strings efficiently.

2. Solution Steps

1. Iterate over the 'haystack' string.

2. For each character in 'haystack', compare the subsequent characters with 'needle'.

3. If a complete match is found, return the starting index.

4. If no match is found by the end of 'haystack', return -1.

3. Code Program

#include <stdio.h>
#include <string.h>

// Function to find the index of the first occurrence of 'needle' in 'haystack'
int strStr(char *haystack, char *needle) {
    int needleLen = strlen(needle); // Length of the needle
    int haystackLen = strlen(haystack); // Length of the haystack

    if (needleLen == 0) return 0; // If needle is empty, return 0

    for (int i = 0; i <= haystackLen - needleLen; i++) { // Iterate over haystack
        int j;
        for (j = 0; j < needleLen; j++) { // Compare substring with needle
            if (haystack[i + j] != needle[j]) break; // Break if characters don't match
        }
        if (j == needleLen) return i; // If full needle is found, return index
    }
    return -1; // Needle not found in haystack
}

int main() {
    char haystack[] = "sadbutsad";
    char needle[] = "sad";
    int result = strStr(haystack, needle); // Find first occurrence
    printf("Output: %d\n", result); // Print the result

    return 0;
}

Output:

0

Explanation:

The program defines a function strStr which iterates over the 'haystack' string, checking each possible substring starting at each index for a match with 'needle'. If a match is found, it returns the starting index of that substring. In our example with 'haystack' as "sadbutsad" and 'needle' as "sad", the first occurrence of "sad" is at index 0. Thus, the output is 0. The function also handles edge cases, like an empty 'needle', returning 0 as per convention since the empty string is considered to be present at every index.