Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

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

Example 2: Input: haystack = "aaaaa", needle = "bba" Output: -1

Solution: Native Search

Slide the pattern over text one by one and check for a match. If a match is not found, then slides by 1 again to check for subsequent matches.

Time complexity: O(m*(n-m+1))

int strStr(string haystack, string needle) {
    if (haystack.size() < needle.size()) return -1;

    for (int i=0; i<=haystack.size() - needle.size(); i++) {
        int j = 0;
        while (j < needle.size() && haystack[i+j] == needle[j]) j++;
        if (j == needle.size()) return i;
    }

    return -1;
}