C++ 8 ms KMP-based O(n) time & O(n) memory solution


  • 127
    S

    We can construct the following string and run KMP algorithm on it:
    (s) + (some symbol not present in s) + (reversed string)

    After running KMP on that string as result we get a vector p with values of a prefix function for each character (for definition of a prefix function see KMP algorithm description). We are only interested in the last value because it shows us the largest suffix of the reversed string that matches the prefix of the original string. So basically all we left to do is to add the first k characters of the reversed string to the original string, where k is a difference between original string size and the prefix function for the last character of a constructed string.

    class Solution {
    public:
        string shortestPalindrome(string s) {
            string rev_s = s;
            reverse(rev_s.begin(), rev_s.end());
            string l = s + "#" + rev_s;
            
            vector<int> p(l.size(), 0);
            for (int i = 1; i < l.size(); i++) {
                int j = p[i - 1];
                while (j > 0 && l[i] != l[j])
                    j = p[j - 1];
                p[i] = (j += l[i] == l[j]);
            }
            
            return rev_s.substr(0, s.size() - p[l.size() - 1]) + s;
        }
    };

  • 1
    R

    I think # is not needed in the middle, just add to the end

    class Solution {
    public:
        string shortestPalindrome(string s) {
            int sn=s.size();
            string rev=s;
            reverse(rev.begin(), rev.end());
            string ss=s+rev+"#";
            int Next[sn*2+1];
            GetNext(ss, Next);
            return rev.substr(0, sn- Next[sn*2])+s;
        }
        void GetNext(string s, int *Next)
        {
            int n=s.size();
            Next[0]=-1;
            for(int i=0;i<n-1;i++)
            {
                int k=Next[i];
                while(k!=-1 && s[k]!=s[i])
                    k=Next[k];
                Next[i+1]=k+1;
            }
        }
    };

  • 0
    C

    I believe # is necessary to be placed at mid to clear the prefix function.
    Test the counterexample : S = aaaa in your case.


  • 0
    R

    so answer is aaaa right? if so, really # is necessary.


  • 0
    R

    Can you explain the effect of vector 'p', I have this code several times, but I can't understand it at all. I will appreciate it If you can tell me the meaning of every item of vector 'p' and how it generate. If it is KMP, where is the pattern string?


  • 0
    V

    We do not need a pattern string to match. Did you see that he or she already construct a string L with reversed s as suffix? we just need to find the prefix array of String L which contains the longest length that prefix and suffix are the same. S.length - prefix[size() - 1] will be how many chars we need to copy to s head(of course in reversed). hope that can help you.

    Check my short loop answer below


  • 2
    V
    for(int i = 1; i < 2 * s.length(); i++) {
            int j = prefix[i-1];
            while(j > 0 && a[i] != a[j])
                j = prefix[j-1];
            if(a[i] == a[j])
                j++;
            prefix[i] = j;
    }
    

    @ricoyoung345, may the for loop like this way is easy to understand.
    Or you can check here : http://blog.csdn.net/pointbreak1/article/details/45931551


  • 0
    R

    thanks, finally got it, but "#" seems indispensible , you may forgot it on your CSDN code.


  • 4
    L

    Thanks for sharing this brilliant solution, here is a Java version:

    public class Solution {
        public String shortestPalindrome(String s) {
            if(s.length() <= 1){ return s; }
            String curs = s + " " + new StringBuilder(s).reverse().toString();
            int[] trace = new int[curs.length()];
            for(int i = 1 ; i < curs.length() ; i++){
                int curindex = trace[i-1];
                while(curindex > 0 && curs.charAt(curindex) != curs.charAt(i)){
                    curindex = trace[curindex-1];
                }
                if(curs.charAt(curindex) == curs.charAt(i)){
                    trace[i] = curindex+1;
                }
            }
            return new StringBuilder(s.substring(trace[curs.length()-1])).reverse().toString() + s;
        }
    }

  • 20

    Here is a different solution, but it's O(n^2), 4ms.

    In order to slove this problem, the key is to get the length of the longest palindromic prefix substring. if the length of s is len, and the length of the longest palindromic prefix substring is longest, the remaining substring will be s.substr(longest, len - longest), than we should reverse the remaining substring and adding it in front of s.

    For example, if s is "abacbbcda", so the longest palindromic prefix substring is "aba"(not "cbbc" because it's not prefix string), and the remaining substring is "cbbcda", we reverse the remaining substring and get "adcbbc", so the result is "adcbbc" + "abacbbcda".

    Please note that the condition in for loop is begin <= len / 2 instead of begin < len, because if begin > len / 2, the substring can not be prefix string, so there is no need to continue.

    class Solution {
    public:
        std::string shortestPalindrome(std::string s) {
    		int len = s.length();
    		if (len < 2)
    			return s;
    		// calculate the length of the longest palindromic prefix substring.
    		int longest = 1, start, end;
    		for (int begin = 0; begin <= len / 2;) {
    			start = end = begin;
    			while (end < len - 1 && s[end + 1] == s[end])
    				++end;
    			begin = end + 1;
    			while (end < len - 1 && start > 0 && s[end + 1] == s[start - 1]) {
    				++end;
    				--start;
    			}
    			// start == 0 means the palindromic substring is also prefix string.
    			if (start == 0 && longest < end - start + 1)
    				longest = end - start + 1;
    		}
    		// reverse the remaining substring and adding it in front of s.
    		std::string remaining = s.substr(longest, len - longest);
    		std::reverse(remaining.begin(), remaining.end());
    		return remaining + s;
        }
    };

  • 0

  • 0
    F

    I think adding a character in the middle is quite unnatural. One can just run KMP on s+rev_s, if the last element of vector p is greater than length of string s, just add the following while loop:

    int m=last element of p;
    while(m>length of s){ m=p[m]; }
    

    The resulting m is the number of elements you need to delete from the reversed string.


  • -2
    J

    Thanks for your idea! This is my solution.

    public class Solution {
            public String shortestPalindrome(String s) {
                
                //calculate the longest palindrome prefix
                int start = 0, end = 0, maxLen = 0;
                for(int i=0; i<=s.length()/2; i++) {
                    start = i;
                    end = i;
                    while(end+1<s.length() && s.charAt(end) == s.charAt(end+1)) {
                        end++;
                    }
                    i = end;
                    while(start >=0 && end<s.length() && s.charAt(end) == s.charAt(start)) {
                        start--;
                        end++;
                    }
                    if (start == -1 && end > maxLen) {
                        maxLen = end;
                    }
                }
                StringBuilder sb = new StringBuilder(s.substring(maxLen));
                sb.reverse();
                sb.append(s);
                return sb.toString();
            }
        }

  • 0
    C

    Nice thought to skip equal value comparisons by moving begin index!

    One small thing, is we could probably optimize by ignoring the check of longest value, as end+! would always be greater than "longest" since we keep moving the end pointer to the right:
    if (start == 0)
    longest = end + 1;


  • 0
    H

    The following line does not compile in your code. What is that "equal"?

    int count = s.length() - equal[2 * s.length()-1];


  • 0
    C

    Great idea! but after several times reading , i still can't get the point of creating string l..... I'll be very grateful if you can reply my question :)


  • 0
    C
    This post is deleted!

  • 0
    N

    I think the While loop may can be replace by if.

    if (j > 0 && l[i] != l[j])
    j = p[j - 1];


  • 0
    S

    no, while loop should be there, algorithm won't work with this if


  • 0
    C

    why O(n^2) is faster than the O(n) using KMP? is it the reason of test cases?


Log in to reply
 

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