KMP CPP Solution


  • 0
    C
    class Solution {
    public:
    
        vector<int> computePrefix(const string &pattern)
        {
            vector<int> prefix(pattern.size()+1, 0);
            
            int state = 0;
            if(pattern.size() >= 1) prefix[1] = 0;
            
            for(int i=2; i <= pattern.size(); i++)
            {
                while(state > 0 && pattern[state] != pattern[i-1])
                    state = prefix[state];
                
                if(pattern[state] == pattern[i-1])
                    state++;
                    
                prefix[i] = state;
            }
            
            return prefix;
        }
        
        int strStr(string haystack, string needle)
        {
            if( !needle.size() ) return 0;
            
            vector<int> prefix = computePrefix(needle);
            
            int state = 0;
            for(int si=0; si < haystack.size(); si++)
            {
                while(state > 0 && needle[state] != haystack[si])
                    state = prefix[state];
                    
                if(needle[state] == haystack[si])
                    state++;
                    
                if(state == needle.size()) return si - needle.size() + 1;
            }
            
            return -1;
        }
    };

Log in to reply
 

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