Advertisement
Zeinab_Hamdy

Untitled

Oct 13th, 2024 (edited)
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.93 KB | None | 0 0
  1. //  #### Zeinab
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define nl "\n"
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ll long long
  9. #define RV return void
  10. #define sz(x) int(x.size())
  11. #define all(v) v.begin(), v.end()
  12. #define rall(v) v.rbegin(), v.rend()
  13. #define cin(v) for(auto&x:v) cin >> x;
  14. #define cout(v) for(auto&x:v) cout << x << " ";
  15.  
  16.  
  17. const int N = 2e5 + 5 , MD = 1e9+7;
  18. int p[2]= {31 , 37} , mod[2] = {MD , MD+2};
  19. int pw[N][2] , inv[N][2];
  20.  
  21.  
  22. int mul(int a , int b , int md){
  23.     return (  1ll * a*b ) % md;
  24. }
  25. int add(int a , int b , int md){
  26.     return ( a%md +b%md ) % md;
  27. }
  28. int fastPower(int a , int b , int md){
  29.     int ret =1;
  30.     while(b){
  31.         if(b & 1 ) ret = mul( ret, a , md);
  32.         a= mul(a , a , md );
  33.         b>>=1;
  34.     }
  35.     return ret ;
  36. }
  37.  
  38. void pre(){
  39.     pw[0][0] = pw[0][1] = inv[0][0] = inv[0][1] =1;
  40.    
  41.     for(int j =0 ;j < 2 ; j++){
  42.         int minv = fastPower(p[j] , mod[j]-2 , mod[j]);
  43.         for(int i =1 ; i < N ; i++){
  44.             pw[i][j] = mul(pw[i-1][j], p[j] , mod[j]);
  45.             inv[i][j] = mul(inv[i-1][j] , minv , mod[j]);
  46.         }
  47.     }
  48. }
  49.  
  50.  
  51.  
  52. struct hashing{
  53.     vector < vector < int > > pref;
  54.  
  55.     hashing(string s , int n){
  56.         pref.assign(n+1 , vector<int>(2));
  57.  
  58.         for(int j =0 ; j < 2 ; j++){
  59.             for(int i =0 ; i < n ; i++){
  60.                 char c = 'a';
  61.                 if (s[i] >='A' and s[i] <='Z') c = 'A';
  62.                 // upper or lower
  63.                 int ch = s[i] - c + 1;
  64.                 pref[i][j] = mul(ch , pw[i][j] , mod[j]);
  65.                 if(i){
  66.                     pref[i][j] = add(pref[i][j] , pref[i-1][j] , mod[j]);
  67.                 }
  68.             }
  69.         }
  70.     }
  71.  
  72.     int calc(int l , int r , int step){
  73.         int ret = pref[r][step];
  74.         if(l){
  75.             ret = (ret - pref[l-1][step] + mod[step]) % mod[step];
  76.         }
  77.         ret = mul(ret , inv[l][step] , mod[step]);
  78.         return ret;
  79.     }
  80.  
  81.     pair < int , int > get_Hash(int l , int r){
  82.         return {calc(l,r,0) , calc(l,r,1)};
  83.     }
  84.    
  85. };
  86.  
  87.  
  88. bool palindrome(string & s , int l , int r){
  89.     while(l <= r) {
  90.         if (s[l] != s[r]) return false;
  91.         l++ , r--;
  92.     }
  93.     return true;
  94. }
  95.  
  96. void solve(){
  97.  
  98.     string s;
  99.     while(cin >> s){
  100.         int n = sz(s);
  101.         if(palindrome(s, 0, n-1)){
  102.             cout << s << nl;
  103.             continue;
  104.         }
  105.         hashing m_hash(s,n);
  106.         int added = 0 , curr1 = 0 , curr2=0, all_len=n ;
  107.  
  108.         while(added < n){
  109.             all_len = n + added + 1;
  110.            
  111.             char c = 'a';
  112.             if (s[added] >='A' and s[added] <='Z') c = 'A';
  113.             int ch = s[added] - c + 1;
  114.             curr1 = add(curr1 , mul(ch , pw[added][0] , mod[0]) , mod[0]);
  115.             curr2 = add(curr2 , mul(ch , pw[added][1] , mod[1]) , mod[1]);
  116.             int cnt = n-1 , curr1_temp =curr1, curr2_temp =curr2;
  117.            
  118.             int index = added+1;
  119.             while(cnt >=(all_len)/2 ){
  120.                 c = 'a';
  121.                 if (s[cnt] >='A' and s[cnt] <='Z') c = 'A';
  122.                 ch = s[cnt] - c + 1;
  123.  
  124.                 curr1_temp = add(curr1_temp , mul(ch , pw[index][0] , mod[0]) , mod[0]);
  125.                 curr2_temp = add(curr2_temp , mul(ch , pw[index][1] , mod[1]) , mod[1]);
  126.  
  127.                 index++ , cnt--;
  128.             }
  129.            
  130.  
  131.             if(make_pair(curr1_temp , curr2_temp) == m_hash.get_Hash(0,(all_len)/2 )){
  132.                 cout << s ;
  133.                 for(int i = added ; i >=0 ; i--) cout << s[i] ;
  134.                 cout << nl;
  135.                 break;
  136.             }
  137.             added++;
  138.         }
  139.     }
  140.    
  141. }
  142. // amanaplanacanalpanama
  143.  
  144. int main(){
  145.     ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);  
  146.    
  147.     int t=1;
  148.         // cin >> t ;
  149.     pre();
  150.     for(int i=1 ; i <= t ; i++){
  151.         // cout << "Case #"<< i <<": ";
  152.         solve();
  153.     }
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement