Advertisement
Josif_tepe

Untitled

Dec 30th, 2023
978
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. const int maxn = 1e5 + 10;
  7. typedef long long ll;
  8. const ll MOD = 922337186621;
  9. const ll alphabet_size = 52;
  10. int n, k;
  11. int rolling_hash(string & s) {
  12.     set<ll> st;
  13.     int n = (int) s.size();
  14.     vector<ll> powers(n + 1, 1);
  15.     for(int i = 1; i <= n; i++) {
  16.         powers[i] = (powers[i - 1] * alphabet_size) % MOD;
  17.     }
  18.     ll hash = 0;
  19.     for(int i = 0; i < k; i++) {
  20.         hash = (hash * alphabet_size + s[i]) % MOD;
  21.     }
  22.     st.insert(hash);
  23.     for(int i = 1; i <= n - k; i++) {
  24.         hash = (hash - powers[k - 1] * s[i - 1]);
  25.         while(hash < 0) {
  26.             hash += MOD;
  27.         }
  28.         hash %= MOD;
  29.         hash = (hash * alphabet_size + s[i + k - 1]) % MOD;
  30.         st.insert(hash);
  31.     }
  32.     return (int) st.size();
  33.    
  34. }
  35.  
  36. int main()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     int t;
  40.     cin >> t;
  41.     while(t--) {
  42.         cin >> n >> k;
  43.         string s;
  44.         cin >> s;
  45.         cout << rolling_hash(s) << endl;
  46.     }
  47.     return 0;
  48. }
  49.  
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement