28. Find the Index of the First Occurrence in a String

Problem Description

Find the first occurrence of a string within another string and return its starting index.

Example 1:

Example 2:

Solution Approach

First, we check if the needle exists in the haystack. If not, we return -1 immediately.

We enumerate each character in the haystack as a potential starting point, and attempt to match from that position:

• If match is successful: Return the starting index
• If match fails: Try the next starting point in haystack

Brute Force Solution

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0  # Return 0 if needle is empty string

        n, m = len(haystack), len(needle)

        # Try matching from each possible starting point in haystack
        for i in range(n - m + 1):
            match = True
            for j in range(m):
                if haystack[i + j] != needle[j]:  # Characters don't match
                    match = False
                    break
            if match:
                return i  # Successful match, return starting index

        return -1  # No match found

KMP Algorithm Solution

The KMP algorithm is a fast string matching algorithm that solves this exact problem: how to quickly find a matching string within an original string.

While the brute force solution has a time complexity of O(m*n), the KMP algorithm achieves O(m+n) complexity. This improvement is possible because KMP can extract and reuse effective information during "incomplete matches" to reduce redundant comparisons.

When a match fails, instead of starting over from the beginning, KMP uses the matching information to move the pattern string to a reasonable position, avoiding unnecessary comparisons.

For a more detailed explanation of the KMP algorithm implementation, please refer to my article on KMP Algorithm Introduction.