Solution UVA: 11475 - Extend to Palindrome

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11475 - Extend to Palindrome	Accepted	C++11	0.020	0.000	1559	4 mins ago

Suggest:

-Use the forward hash and reverse hash

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int base= 31, mod= 1000111000;

int f(char x){

    return x-'a'+1;

}

int32_t main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    string s;

    while(cin >> s){

       

        int l, hash_x= 0, hash_y= 0, base_y= 1;

        for(int i=s.size()-1; i>=0; i--){

           

            hash_x = (hash_x * base + f(s[i]))%mod;

            hash_y = (f(s[i])*base_y + hash_y)%mod;

            base_y= (base*base_y)%mod;

           

            if (hash_x == hash_y) l= i-1;

        }

       

        cout<<s;

        if (l>=0) for(int i=l; i>=0; i--) cout<<s[i];

        cout<<"\n";

    }

}