KMP Algorithm using C++


  • 3
    T
    class Solution {
    public:
        int strStr(string haystack, string needle) {
            if(needle.empty()) return 0;
            if(haystack.empty()) return -1;
            vector<int> pi(needle.size(), 0);
            //KMP-algorithm:
            //Pre-process
            int k = 0, i;
            for(i = 1; i < needle.size(); i++) {
                while(k > 0  && needle[k] != needle[i]) k = pi[k - 1];
                if(needle[k] == needle[i]) pi[i] = ++k;
            }
            k = 0;
            //Matching
            for(i = 0; i < haystack.size(); i++) {
                while(k > 0 && haystack[i] != needle[k]) k = pi[k - 1];
                if(haystack[i] == needle[k]) k++;
                if(k == needle.size()) return i - needle.size() + 1;
            }
            return -1;
        }
    };

  • 0
    This post is deleted!

  • 0

    I change " while(k > 0 && needle[k] != needle[i]) k = pi[k - 1];" to " while(k > 0 && needle[k] != needle[i]) k =0;" it also acceptted.Is that right ?why?


  • 0
    T

    That is also right, but less efficient. The array "needle" stored the information we've already known. Changing "k = pi[k - 1]" to "k = 0", it means you skip the step that search the information we got through previous computation. So, the answer is also right, but the algorithm could cost more time due to repeated computation.


  • 0

    Can you give me an example?Thank you very much!!!非常非常感谢~


  • 0

    If needle does not have a continuous repeat of the elements ,such as needle="ABCDABCABC" ,there is no different between "k = pi[k - 1]" and "k = 0",
    I have come up with an example:haystack=AAABAAABAAAE, needle=AAABAAAE;if "k = 0",pi=01201230;if "k = pi[k - 1]",pi=01202340.It cost an extra step to find "AAABAAAE" in"AAABAAABAAAE" when we take "k = 0",is that right ?


  • 0
    T
    This post is deleted!

  • 0
    This post is deleted!

Log in to reply
 

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