My 4ms C++ solution, it used the kmp algorithm.


  • 0
    D

    class Solution {
    public:

    // get the "next" array
    vector<int> getNext(string &s) {
        int length = s.size();
        vector<int> next(length);
        next[0] = 0;
        for (int i = 1,q = 0; i < length;i++) {
            while (q > 0 && s[i] != s[q]) 
                q = next[q-1];
            if (s[i] == s[q]) 
                q++;
            next[i] = q;
        }
        return next;
    }
    // use kmp algorithm to judge if the first string can match the second string
    int kmp(string &s1,string &s2) {
        int length1 = s1.size(),length2 = s2.size();
        if (length1 < length2) 
            return false;
        vector<int> next = getNext(s2);
        for (int i = 0, q= 0; i < length1;i++) {
            while (q > 0 && s1[i] != s2[q]) 
                q = next[q-1];
            if (s1[i] == s2[q]) 
                q++;
            if (q == length2) 
                return i-q+1;
        }
        return -1;
    }
    
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;
        if (haystack.empty()||haystack.size() < needle.size()) return -1;
        return kmp(haystack,needle);
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.