Implement strStr()

LeetCode #28

Description:

Implement strStr().

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

Example:

Note

if both are empty, return 0;

Idea:

Method 1, Naive, time O(nm) See code.

Method 2, KMP, time O(n)

Code:

Method 1

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(haystack.empty() && needle.empty()) return 0; 
        if(haystack.size()<needle.size()) return -1;

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

        return -1;
    }
};