Find the longest palindrome prefix.

  • 1

    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;
        for(int j=res-1; j>=0; j--){
            p = s[size-1-j]+p;
        return p;

  • 0

    @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
    This post is deleted!

  • 0

    @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.