Implement strStr() - Naive Pattern Matching

Problem

Implement strStr(): return the index of the first occurrence of a needle string inside a haystack string, or -1 if not found (naive pattern matching).

Input:  haystack = "hello", needle = "ll"
Output: 2

Python Solution

def str_str(haystack, needle):
    n, m = len(haystack), len(needle)
    for i in range(n - m + 1):
        if haystack[i:i + m] == needle:
            return i
    return -1

C++ Solution

int strStr(string haystack, string needle) {
    int n = haystack.size(), m = needle.size();
    for (int i = 0; i <= n - m; i++) {
        if (haystack.substr(i, m) == needle) return i;
    }
    return -1;
}

Java Solution

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i <= n - m; i++) {
            if (haystack.substring(i, i + m).equals(needle)) return i;
        }
        return -1;
    }
}

Complexity

Time: O(n · m) in the worst case — for each of the n-m+1 starting positions, comparing up to m characters. Space: O(1) — no extra structure, aside from language-specific substring copies.