4ms c++ code, using KMP algorithm


  • 2
    E

    My first submission exceeded the time limit: O(m*n)

    class Solution {
    public:
        int strStr(string haystack, string needle) {
            int haSize = haystack.size();
            int neSize = needle.size();
            if (neSize == 0) return 0;
            int i, j;
            for (i = 0; i < haSize; i++)
                if (haystack[i] == needle[0]) {
                    for (j = 1; j < neSize; j++)
                        if (haystack[i+j] != needle[j])
                            break;
                    if (j == neSize) return i;
                }
            return -1;
        }
    };
    

    The following is KMP algorithm, it's really fast: O(m+n). I referenced the video on Youtube:
    https://www.youtube.com/watch?v=kBW6oPaVjq0

    class Solution {
    public:
        // compute Prefix function
        vector<int> PrefixFun(string needle) {
            int m = needle.size();
            vector<int> pi(m);
            int k = 0;
            for (int i = 1; i < m; i++) {
                while (k > 0 && needle[k] != needle[i])
                    k = pi[k-1];
                if (needle[k] == needle[i])
                    k = k+1;
                pi[i] = k;
            }
            return pi;
        }
    
        // KMP(Knuth-Morris-Pratt) algorithm
        int strStr(string haystack, string needle) {
            int haSize = haystack.size();
            int neSize = needle.size();
            if (neSize == 0) return 0;
            vector<int> PF = PrefixFun(needle);
            int i = 0, j = 0;
            while (i < haSize) {
                if (haystack[i] == needle[j]) {
                    if (j == neSize-1) return i-neSize+1;
                    j++; i++;
                }
                else if (j == 0) i++;
                else j = PF[j-1];
            }
            return -1;
        }
    };

Log in to reply
 

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