Share my C++ O(N) KMP method


  • -4
    V

    The Key idea is to generate the prefix suffix match array.
    Please note that I add an "#" between the string and the reversed one, in case of too long matched suffix.

    class Solution {
    public:
        string shortestPalindrome(string s) {
            string p=s;
            reverse(p.begin(),p.end());
            p=s+"#"+p;
            vector<int> next(p.size()+1,0);	//
            getNext(p,next);
            return p.substr(s.size()+1,s.size()-next.back())+s;
        }
        //prefix suffix match, O(N)
    	void getNext(string &p, vector<int> &next){
    		next[0]=-1;
    		int k=-1,j=0,len=next.size();
    		while(j<len-1){
    			//p[k] denotes prefix, p[j] denotes suffix
    			if(k==-1||p[j]==p[k])next[++j]=++k;
    			else k=next[k];
    		}
    	}
    };

  • 0
    C

    Wrong thread, OP :-p


  • 0
    V

    Sorry, can you present more details?


  • 0
    C

    This thread is for Sliding Window Maximum


Log in to reply
 

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