Imagine you have two pieces of text: a long one called "haystack" and a short one called "needle".

• Your job is to find if the short text (needle) is hiding anywhere inside the long text (haystack).
• First, we check how long each piece of text is:
  • We call the length of the haystack "n"
  • We call the length of the needle "m"
• If the needle is empty (has no letters), we say we found it right at the beginning.
• Now, we start looking through the haystack, letter by letter:
  • We only need to look up to a point where there's enough space left for the needle to fit.
• At each spot in the haystack, we start comparing letters:
  • We check if the first letter of the needle matches
  • If it does, we check the next letter, and the next, and so on
  • If all letters match, we found the needle! We tell where it starts in the haystack.
  • If any letter doesn't match, we stop and move to the next spot in the haystack.
• If we finish looking through the whole haystack and didn't find the needle, we say it's not there.

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(); // Get the length of the larger string (haystack)
        int m = needle.size();   // Get the length of the smaller string (needle)

        // If needle is an empty string, return 0 (it is found at the beginning of haystack)
        if (m == 0) return 0;

        // Loop through the haystack up to the point where the remaining characters are less than needle's length
        for (int i = 0; i <= n - m; i++) {
            // Check if the substring of haystack starting from i matches the needle
            for (int j = 0; j < m; j++) {
                // If the characters don't match, break out of the inner loop
                if (needle[j] != haystack[i + j]) {
                    break;
                }
                // If we have compared all characters of needle and they match, return the start index i
                if (j == m - 1) {
                    return i;
                }
            }
        }
        // If we finish the loop without finding the needle, return -1
        return -1;
    }
};

Step-by-Step Explanation:

1. Variables Setup:

   • n is the length of the haystack string.
   • m is the length of the needle string.

2. Edge Case:

   • If needle is empty (m == 0), the function returns 0 because an empty string is considered to be at the start of any string.

3. Main Loop:

   • We start a loop with i going from 0 to n - m. This ensures we do not start comparing past the point where needle can no longer fit in the remaining part of haystack.

4. Inner Loop:

   • For each position i in haystack, we check if the substring starting at i matches needle.
   • We use another loop with j going from 0 to m - 1 to compare each character of needle with the corresponding character in haystack.

5. Mismatch Check:

   • If at any position j the characters do not match (needle[j] != haystack[i + j]), we break out of the inner loop and move to the next position i.

6. Full Match Check:

   • If we successfully compare all characters (j == m - 1), it means needle is found in haystack starting at index i. We return i.

7. Not Found:

   • If the loop completes and needle is not found, we return -1.

DRY RUN with an Example ! you can understand Better !