KMP Algorithm,

Pre-compute and create the suffix equal to prefix table Next. Then if mismatch, run back the pointer of needle string according to the prefix table on the mismatch place. (e.g. mismatch at j, needle string pointer will run back to Next[j]).

If mismatch at the last one, return -1.

C++ solution:



class Solution {
public:
        int next[100000];
        void KMP(string &str)
        {
                int pointer = 0;
                next[0] = -1;

                for(int i = 1; i < str.length(); ++i)
                {
                        if(pointer > 0) next[i] = pointer;
                        else next[i] = 0;

                        if(str[i] == str[pointer]) pointer++;
                        else pointer = 0;
                }
        }

        int strStr(string haystack, string needle) {
                int l1 = haystack.length();
                int l2 = needle.length();

                if(l2 == 0) return 0;
                if(l1 < l2) return -1;

                KMP(needle);

                int i = 0, j = 0;

                while(i < l1)
                {
                        while(j < l2)
                        {
                                if(haystack[i] != needle[j])
                                {
                                        if(next[j] >= 0) j = next[j];
                                        else { j = 0; ++i; }
                                        break;
                                }
                                else { ++j; ++i; }
                        }
                        if(j == l2) return i - j;
                }
                return -1;
        }
};

Leave a Reply

Your email address will not be published. Required fields are marked *