Find the longest palindrome prefix.


  • 1
    L

    I use hash to check whether it is palindrome.

    string shortestPalindrome(string s) {
        typedef unsigned long long ull; 
        const ull B = (ull)(1e9+7);
        int size = s.size();
        ull l = 0, r = 0;
        vector<ull> Pow(size+1, 1);
        for(int i=1; i<=size; i++) Pow[i] = Pow[i-1] * B;
        int M = 0;
        for(int i=0; i<size; i++){
            l = l*B + s[i];
            r = r + s[i] * Pow[i];
            if(l == r){
                M = i+1;
            }
        }
        int res = size-M;
        string p = s;
        cout<<res<<endl;
        for(int j=res-1; j>=0; j--){
            p = s[size-1-j]+p;
        }
        return p;
    }

  • 0
    A

    @layor Indeed I like the way you think to use hashing in this problem. But I have one suggestion. That is don't use 1e9+7 as the base but as the modulo. I can think about that you are using 2^64 as the default modulo as you don't care the overflow problem. But it is suggested that the modulo is better to be a prime.


  • 0
    L
    This post is deleted!

  • 0
    L

    @actionlee0405 Thanks for your suggestion


Log in to reply
 

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