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

1. Introduction

In this post, we will explore a common string searching problem in C programming - finding the index of the first occurrence of a substring (needle) in a given string (haystack). This problem is fundamental in text processing, searching algorithms, and is widely applicable in fields like data mining and web searching.

Problem

Given two strings, needle and haystack, the task is to return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

2. Solution Steps

1. Check if needle is empty. If it is, return 0 since an empty string is always found at the first position.

2. Iterate through haystack and for each character, check if the substring starting from that character matches needle.

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

4. If no match is found throughout the loop, 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 needleLength = strlen(needle);
    int haystackLength = strlen(haystack);

    if (needleLength == 0) {
        return 0; // Needle is an empty string
    }

    for (int i = 0; i <= haystackLength - needleLength; i++) {
        int found = 1;
        for (int j = 0; j < needleLength; j++) {
            if (haystack[i + j] != needle[j]) {
                found = 0;
                break;
            }
        }
        if (found) {
            return i; // Found needle at index i
        }
    }
    return -1; // Needle not found
}

// Main function to test the strStr function
int main() {
    char haystack1[] = "sadbutsad";
    char needle1[] = "sad";
    printf("First occurrence index (Example 1): %d\n", strStr(haystack1, needle1));

    char haystack2[] = "leetcode";
    char needle2[] = "leeto";
    printf("First occurrence index (Example 2): %d\n", strStr(haystack2, needle2));

    return 0;
}

Output:

First occurrence index (Example 1): 0
First occurrence index (Example 2): -1

Explanation:

1. Check if needle is empty and return 0 if it is.

2. Iterate through haystack to find the starting index of needle.

3. For each character in haystack, compare it with the corresponding character in needle.

4. If all characters of needle are found consecutively in haystack, return the starting index.

5. If no match is found, return -1.

6. The main function tests the strStr function with two examples and prints the results.