My C++ brute-force, Robin-Karp, KMP codes


  • 2
    D

    Brute-force version

    class Solution {
    public:
        int strStr(string haystack, string needle) {
            int i, hSize = haystack.size(), nSize = needle.size();
            if(hSize<nSize) return -1;
            if(!nSize) return 0;
            for(i=0; i<=hSize-nSize && haystack.substr(i,nSize)!= needle;++i);
            return i<=hSize-nSize?i:-1;
        }
    };
    

    Robin-Karp version (followed WiKI with a simple hash function, https://en.wikipedia.org/wiki/Rabin–Karp_algorithm)

    class Solution {
    private:
        inline char hash(const string &s)
        {
            char all =0;
            for(auto i=0;i<s.size();++i)    all ^=s[i];
            return all;
        }
        
    public:
        int strStr(string haystack, string needle) {
            int i, hSize = haystack.size(), nSize = needle.size();
            char target;
            if(hSize<nSize) return -1;
            if(!nSize) return 0;
            target = hash(needle);
            for(i=0; i<=hSize-nSize;++i)
            {
                if(hash(haystack.substr(i,nSize)) == target && haystack.substr(i,nSize)== needle) break;
            }
            return i<=hSize-nSize?i:-1;
        }
    };
    

    Standard KMP algorithm (followed Wiki, https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm)

       class Solution {
        private:
            void buildKMPTable(const string & s, vector<int> &KMP_Table)
            {
                int sSize = s.size(), i=2, j=0;
                KMP_Table[0] = -1;
                if(sSize>1) KMP_Table[1] = 0;
                while(i<sSize)
                {
                    if(s[i-1]==s[j]) KMP_Table[i++] = ++j;
                    else if(j>0) j = KMP_Table[j];
                    else KMP_Table[i++] = 0;
                }
            }
        public:
            int strStr(string haystack, string needle) {
                int start=0, i=0, hSize = haystack.size(), nSize = needle.size();
                if(hSize<nSize) return -1;
                if(!nSize) return 0;
                vector<int> KMP_Table(nSize, 0);
                buildKMPTable(needle, KMP_Table);
                while(start<=hSize-nSize)
                {
                    if(haystack[start+i]==needle[i])
                    {
                        if(++i == nSize) return start;
                    }
                    else
                    {
                        start = start+i-KMP_Table[i];
                        i= i>0?KMP_Table[i]:0;    
                    }
                }
                return -1;
            }
        };

  • 0
    B

    Hi, I have a question for your Rolling Hash algorithm, why you ^ all elements in the array to get the hash? Thanks


Log in to reply
 

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