Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // #### Zeinab
- #include<bits/stdc++.h>
- using namespace std;
- #define nl "\n"
- #define fi first
- #define se second
- #define pb push_back
- #define ll long long
- #define RV return void
- #define sz(x) int(x.size())
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define cin(v) for(auto&x:v) cin >> x;
- #define cout(v) for(auto&x:v) cout << x << " ";
- const int N = 2e5 + 5 , MD = 1e9+7;
- int p[2]= {31 , 37} , mod[2] = {MD , MD+2};
- int pw[N][2] , inv[N][2];
- int mul(int a , int b , int md){
- return ( 1ll * a*b ) % md;
- }
- int add(int a , int b , int md){
- return ( a%md +b%md ) % md;
- }
- int fastPower(int a , int b , int md){
- int ret =1;
- while(b){
- if(b & 1 ) ret = mul( ret, a , md);
- a= mul(a , a , md );
- b>>=1;
- }
- return ret ;
- }
- void pre(){
- pw[0][0] = pw[0][1] = inv[0][0] = inv[0][1] =1;
- for(int j =0 ;j < 2 ; j++){
- int minv = fastPower(p[j] , mod[j]-2 , mod[j]);
- for(int i =1 ; i < N ; i++){
- pw[i][j] = mul(pw[i-1][j], p[j] , mod[j]);
- inv[i][j] = mul(inv[i-1][j] , minv , mod[j]);
- }
- }
- }
- struct hashing{
- vector < vector < int > > pref;
- hashing(string s , int n){
- pref.assign(n+1 , vector<int>(2));
- for(int j =0 ; j < 2 ; j++){
- for(int i =0 ; i < n ; i++){
- char c = 'a';
- if (s[i] >='A' and s[i] <='Z') c = 'A';
- // upper or lower
- int ch = s[i] - c + 1;
- pref[i][j] = mul(ch , pw[i][j] , mod[j]);
- if(i){
- pref[i][j] = add(pref[i][j] , pref[i-1][j] , mod[j]);
- }
- }
- }
- }
- int calc(int l , int r , int step){
- int ret = pref[r][step];
- if(l){
- ret = (ret - pref[l-1][step] + mod[step]) % mod[step];
- }
- ret = mul(ret , inv[l][step] , mod[step]);
- return ret;
- }
- pair < int , int > get_Hash(int l , int r){
- return {calc(l,r,0) , calc(l,r,1)};
- }
- };
- bool palindrome(string & s , int l , int r){
- while(l <= r) {
- if (s[l] != s[r]) return false;
- l++ , r--;
- }
- return true;
- }
- void solve(){
- string s;
- while(cin >> s){
- int n = sz(s);
- if(palindrome(s, 0, n-1)){
- cout << s << nl;
- continue;
- }
- hashing m_hash(s,n);
- int added = 0 , curr1 = 0 , curr2=0, all_len=n ;
- while(added < n){
- all_len = n + added + 1;
- char c = 'a';
- if (s[added] >='A' and s[added] <='Z') c = 'A';
- int ch = s[added] - c + 1;
- curr1 = add(curr1 , mul(ch , pw[added][0] , mod[0]) , mod[0]);
- curr2 = add(curr2 , mul(ch , pw[added][1] , mod[1]) , mod[1]);
- int cnt = n-1 , curr1_temp =curr1, curr2_temp =curr2;
- int index = added+1;
- while(cnt >=(all_len)/2 ){
- c = 'a';
- if (s[cnt] >='A' and s[cnt] <='Z') c = 'A';
- ch = s[cnt] - c + 1;
- curr1_temp = add(curr1_temp , mul(ch , pw[index][0] , mod[0]) , mod[0]);
- curr2_temp = add(curr2_temp , mul(ch , pw[index][1] , mod[1]) , mod[1]);
- index++ , cnt--;
- }
- if(make_pair(curr1_temp , curr2_temp) == m_hash.get_Hash(0,(all_len)/2 )){
- cout << s ;
- for(int i = added ; i >=0 ; i--) cout << s[i] ;
- cout << nl;
- break;
- }
- added++;
- }
- }
- }
- // amanaplanacanalpanama
- int main(){
- ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
- int t=1;
- // cin >> t ;
- pre();
- for(int i=1 ; i <= t ; i++){
- // cout << "Case #"<< i <<": ";
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement