Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- const int maxn = 1e5 + 5;
- ull h[2][maxn];
- ull deg[maxn];
- const ull p = 409;
- ull get_hash(int l, int r, int num)
- {
- assert(deg[r - l + 1] > 0);
- assert(r - l + 1 >= 0);
- return h[num][r + 1] - h[num][l] * deg[r - l + 1];
- }
- int main()
- {
- char buf[maxn];
- scanf("%s", buf);
- string s1(buf);
- scanf("%s", buf);
- string s2(buf);
- string cycle_shifts = s2 + s2;
- int n = (int)s2.size();
- deg[0] = 1;
- assert((int)cycle_shifts.size() == 2 * n);
- for(int i = 0; i < (int)cycle_shifts.size(); i++)
- {
- h[0][i + 1] = h[0][i] * p + cycle_shifts[i];
- deg[i + 1] = deg[i] * p;
- }
- for(int i = 0; i < (int)s1.size(); i++)
- {
- h[1][i + 1] = h[1][i] * p + s1[i];
- }
- vector<ull>hashes(n);
- for(int i = 0; i < n; i++)
- {
- hashes[i] = get_hash(i, i + n - 1, 0);
- }
- assert((int)hashes.size() == n);
- sort(hashes.begin(), hashes.end());
- int ans = 0;
- for(int i = 0; i < (int)s1.size() - n + 1; i++)
- {
- assert(i + n - 1 < (int)s1.size());
- ull curHash = get_hash(i, i + n - 1, 1);
- if(binary_search(hashes.begin(), hashes.end(), curHash))
- ans++;
- }
- printf("%d", ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement