Advertisement
Guest User

Untitled

a guest
Jun 27th, 2022
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  2. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. #define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  9. #define pb push_back
  10. #define mp make_pair                                
  11. #define F first
  12. #define S second
  13. #define sz(x) (int)(x.size())                        
  14. #define all(x) x.begin(), x.end()        
  15.  
  16. typedef long long ll;
  17. typedef unsigned long long ull;
  18.  
  19.  
  20. const ll INF = LLONG_MAX;
  21. const int inf = INT_MAX;
  22. const int N = 3e5+5;
  23. const int MOD = 1e9+7;
  24. const double EPS = 1e-9;                
  25. const int p = 31;                                
  26.  
  27. vector <ll> p_pow(N), hash_s(N);
  28. ll hash_t, pp = 1;
  29.  
  30. void solve(){
  31.     string s, t;
  32.     cin >> s >> t;
  33.  
  34.     int n = sz(s);
  35.  
  36.     p_pow[0] = 1;      
  37.    
  38.     for(int i = 1; i < n; i++)
  39.         p_pow[i] = p_pow[i-1] * p;
  40.  
  41.     for(int i = 0; i < n; i++){
  42.         hash_s[i] = (s[i] - 'a' + 1) * p_pow[i];
  43.         if(i)
  44.             hash_s[i] += hash_s[i-1];
  45.     }
  46.              
  47.     for(int i = 0; i < sz(t); i++){
  48.         hash_t += (t[i]-'a' + 1) * pp;
  49.         pp *= 31;
  50.     }
  51.  
  52.     //lets imagine that s = "ababa" and t = "ba"
  53.     //and s[1..2] = t;
  54.  
  55.     int l = 1, r = 2;                  
  56.    
  57.     cout << hash_t << ' ' << hash_s[r] - hash_s[l] * pow(p, r-l+1);
  58.  
  59.  
  60.  
  61. }
  62.                
  63. int main(){
  64.     speed;      
  65.  
  66.     int T = 1;  
  67.    
  68.     while(T--)
  69.         solve();
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement