Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <vector>
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1e5 + 10;
- typedef long long ll;
- const ll MOD = 922337186621;
- const ll alphabet_size = 52;
- int n, k;
- int rolling_hash(string & s) {
- set<ll> st;
- int n = (int) s.size();
- vector<ll> powers(n + 1, 1);
- for(int i = 1; i <= n; i++) {
- powers[i] = (powers[i - 1] * alphabet_size) % MOD;
- }
- ll hash = 0;
- for(int i = 0; i < k; i++) {
- hash = (hash * alphabet_size + s[i]) % MOD;
- }
- st.insert(hash);
- for(int i = 1; i <= n - k; i++) {
- hash = (hash - powers[k - 1] * s[i - 1]);
- while(hash < 0) {
- hash += MOD;
- }
- hash %= MOD;
- hash = (hash * alphabet_size + s[i + k - 1]) % MOD;
- st.insert(hash);
- }
- return (int) st.size();
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- int t;
- cin >> t;
- while(t--) {
- cin >> n >> k;
- string s;
- cin >> s;
- cout << rolling_hash(s) << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement