Nlogn approach , Binary Search + hashing


#1
typedef pair<int, int> pii;
using ll = long long;
ll p = 31LL, mod = 1e9 + 7LL, p_inv; 

ll bin_exp(ll num, ll pw){
    ll res = 1;
    while(pw){
        if(pw & 1){
            res = res * num;
            res %= mod;
        }
        num *= num;
        num %= mod;
        pw >>= 1;
    }
    return res;
}

ll INV(ll num, ll mod){
    return bin_exp(num, mod - 2LL);
}

pii Binary_Search(string &s, bool isOdd){
    int n = s.size();
    int l = 1, r = ((n + isOdd) >> 1), ans_i = -1, ans_l = 0;
    while(l <= r){
        int mid = (l + r) / 2, len = 2*mid - isOdd;
        ll fr_h = 0LL, bk_h = 0LL, p_fac = 1LL;
        for(int i = 0; i < len; i ++){
            p_fac *= p;
            p_fac %= mod;
            fr_h += (((ll)(s[i] - 'a')*p_fac) % mod);
            fr_h %= mod;
            
            bk_h *= p;
            bk_h %= mod;
            bk_h += ((ll)(s[i] - 'a') * p);
            bk_h %= mod;
        }
        bool f = false;
        if(fr_h == bk_h){
            ans_i = 0;
            f = true;
        }
        for(int i = 1; i <= n - len; i ++){
            if(f)
                break;
            fr_h = (fr_h - ((ll)(s[i - 1] - 'a')* p) + mod) % mod;
            fr_h %= mod;
            fr_h *= p_inv;
            fr_h %= mod;
            fr_h += (((ll)(s[i + len - 1] - 'a') * p_fac) % mod);
            fr_h %= mod;
            
            bk_h = (bk_h - (((ll)(s[i - 1] - 'a') * p_fac) % mod) + mod) % mod;
            bk_h %= mod;
            bk_h *= p;
            bk_h %= mod;
            bk_h += ((ll)(s[i + len - 1] - 'a') * p);
            bk_h %= mod;
            
            if(fr_h == bk_h){
                ans_i = i;
                f = true;
            }
        }
        if(f){
            ans_l = len;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    return pii(ans_l, -ans_i);
}

string Solution::longestPalindrome(string A) {
    p_inv = INV(p, mod);
    pii ans = max(Binary_Search(A, true), 
        Binary_Search(A, false));
    string f_ans;
    if(ans.first == 0)
        return f_ans;
    return A.substr(-ans.second, ans.first);
}