Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
- #include <bits/stdc++.h>
- using namespace std;
- #define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- #define pb push_back
- #define mp make_pair
- #define F first
- #define S second
- #define sz(x) (int)(x.size())
- #define all(x) x.begin(), x.end()
- typedef long long ll;
- typedef unsigned long long ull;
- const ll INF = LLONG_MAX;
- const int inf = INT_MAX;
- const int N = 3e5+5;
- const int MOD = 1e9+7;
- const double EPS = 1e-9;
- const int p = 31;
- vector <ll> p_pow(N), hash_s(N);
- ll hash_t, pp = 1;
- void solve(){
- string s, t;
- cin >> s >> t;
- int n = sz(s);
- p_pow[0] = 1;
- for(int i = 1; i < n; i++)
- p_pow[i] = p_pow[i-1] * p;
- for(int i = 0; i < n; i++){
- hash_s[i] = (s[i] - 'a' + 1) * p_pow[i];
- if(i)
- hash_s[i] += hash_s[i-1];
- }
- for(int i = 0; i < sz(t); i++){
- hash_t += (t[i]-'a' + 1) * pp;
- pp *= 31;
- }
- //lets imagine that s = "ababa" and t = "ba"
- //and s[1..2] = t;
- int l = 1, r = 2;
- cout << hash_t << ' ' << hash_s[r] - hash_s[l] * pow(p, r-l+1);
- }
- int main(){
- speed;
- int T = 1;
- while(T--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement