Simple and clean c++ KMP implementation


  • 3
    L
        int strStr(string haystack, string needle) {
        const int size_h = haystack.size();
        const int size_n = needle.size();
        if (0 == size_n) return 0;
        vector<int> p(size_n, 0);
        for (int i = 1; i < size_n; i++) {
            int pos = p[i-1];
            while (pos > 0 && needle[i] != needle[pos]) pos = p[pos-1];
            if (needle[i] == needle[pos]) p[i] = pos + 1;
        }
        int idn = 0, idh = 0;
        for (idh; idh < size_h; idh++){
            while (idn > 0 && needle[idn] != haystack[idh]) idn = p[idn-1];
            if (needle[idn] == haystack[idh]) idn++;
            if (idn == size_n) return idh - size_n + 1;
        }   
        return -1;
    }

Log in to reply
 

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