Implement strStr

Brute Force

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

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

The code above uses the simplest approach. It compares characters one by one. When we find a match, we advance both pointers. When we hit a mismatch, we reset and start over from the next position in the main string.

This works well for most cases. The time complexity is O(m*n) where m and n are the lengths of the strings. For typical inputs, it runs fast enough.

KMP

The Knuth-Morris-Pratt algorithm improves on this. It avoids rechecking characters we already know don’t match. The key insight: when a mismatch happens, we can use information about the pattern itself to skip ahead.

KMP preprocesses the needle to build a “failure function” that tells us how much to shift when we encounter mismatches. This gives us O(m+n) time complexity in the worst case.

For many practical applications, the brute force version suffices. But understanding KMP shows how algorithmic thinking can solve problems more elegantly.