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

1. Introduction

This blog post focuses on a common string manipulation problem in C++: finding the index of the first occurrence of one string (needle) within another (haystack). This problem is essential for understanding string searching algorithms.

Problem

The challenge is to write a function in C++ that returns 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 so, return 0 since an empty string is always found at the first position.

2. Iterate through haystack to find the starting position where needle matches.

3. For each potential starting position in haystack, check if needle can be found entirely from that position.

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

5. If no match is found after checking all possible positions, return -1.

3. Code Program

#include <iostream>
using namespace std;

// Function to find the index of the first occurrence of needle in haystack
int strStr(string haystack, string needle) {
    if (needle.empty()) return 0; // An empty needle is always found at position 0

    int n = haystack.size(), m = needle.size();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        // Check for needle in haystack starting from position i
        for (; j < m; j++) {
            if (haystack[i + j] != needle[j]) break;
        }
        if (j == m) return i; // If the whole needle is found
    }
    return -1; // Needle not found in haystack
}

int main() {
    string haystack = "hello";
    string needle = "ll";
    cout << "Index of first occurrence: " << strStr(haystack, needle) << endl;
    return 0;
}

Output:

Index of first occurrence: 2

Explanation:

1. The input haystack is "hello" and the needle is "ll".

2. The function iterates over haystack, looking for the start of needle.

3. At index 2 of haystack, the substring "ll" matches needle.

4. The function returns 2, the index where needle is first found in haystack.

5. If needle were not found, the function would return -1, indicating no match.