Share my C++ O(N) KMP method


  • 3
    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
    P

    KMP is the most elegant solution for this question. Bravo!


Log in to reply
 

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