Clean KMP solution in C++


  • 2

    If you are resolved to understand it, then read this wiki first and then this easy-understanding post. Good luck!

    class Solution {
    public:
        int strStr(string haystack, string needle) 
        {
            int nLen = needle.length(), hLen = haystack.length();
            if(nLen == 0) return 0;
            int next[nLen]{0};
            next[0] = 0;
            for(int i = 1; i < nLen; ++i)
            {
                int j = next[i-1];
                while(j>0 && needle[i]!=needle[j]) j = next[j-1];
                next[i] += j+(needle[i]==needle[j]); //the length of the matched prefix;
            }
            int i = 0, j = 0;
            while(i < hLen)
            {
                while(haystack[i]!=needle[j] && j>0) j = next[j-1];
                if(haystack[i] == needle[j]) j++;
                if(j == nLen) return i-j+1;
                i++;
            }
            return -1;
        }
    };

  • 0
    H
    class Solution {
    private:
        void KMP_table(const string& w, int* T)
        {
            if (w.length() == 0)
                return;
            if (w.length() == 1)
            {
                T[0] = -1;
                return;
            }
            if (w.length() == 2)
            {
                T[0] = -1;
                T[1] = 0;
                return;
            }
            T[0] = -1;
            T[1] = 0;
            int pos = 2, cnd = 0;
            while (pos < w.length())
            {
                if (w[pos - 1] == w[cnd])
                    T[pos++] = ++cnd;
                else if (cnd > 0)
                    cnd = T[cnd];
                else
                    T[pos++] = 0;
            }
        }
    public:
        int strStr(string haystack, string needle) {
            if (haystack.length() == 0 || needle.length() == 0 || needle.length() > haystack.length())
                return haystack.length();
            int m = 0, i = 0;
            int* T = new int[needle.length()];
            KMP_table(needle, T);
            while (m + i < haystack.length())
            {
                if (haystack[m + i] == needle[i])
                {
                    if (i == haystack.length() - 1)
                        return m;
                    ++i;
                }
                else
                {
                    if (T[i] > -1)
                    {
                        m = m + i - T[i];
                        i = T[i];
                    }
                    else
                    {
                        ++m;
                        i = 0;
                    }
                }
            }
            delete[] T;
            return haystack.length();
        }
    };
    

    Thank you for your code! I used the method of wiki you methioned above,but it was wrong when I submitted.Could you please help me to find where the bug is?


  • 0

    @honglixx3 You really should read the second post, if you are trying to implement it. Wiki here is just for you to know what is KMP not here to help you to implement it yourself. Good luck!

    B.T.W. your code here is quite complicated, you can achieve better after your reading the second post, I believe. Besides, my solution here is a good reference here.


Log in to reply
 

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