#include "poszukiwania.h" #include "message.h" #include <iostream> #include <vector> using namespace std; typedef long long ll; const ll P = 90000007; ll Hasz(vector<ll>& H, vector<ll>& p, ll po, ll ko) { return H[po] - p[ko - po + 1] * H[ko + 1]; } int main() { ios_base::sync_with_stdio(0); ll n = SignalLength(); vector<ll> S(n); for (int i = 0; i < n; ++i) S[i] = SignalAt(i + 1); ll m = SeqLength(); vector<ll> M(m); for (int i = 0; i < m; ++i) M[i] = SeqAt(i + 1); ll dlo = max(n, m); vector<ll> p(dlo); p[0] = 1; for (int i = 1; i < dlo; ++i) p[i] = p[i - 1] * P; vector<ll> H1(n + 1); H1[n] = 0; for (int i = n - 1; i >= 0; --i) H1[i] = H1[i + 1] * P + S[i]; vector<ll> H2(m + 1); H2[m] = 0; for (int i = m - 1; i >= 0; --i) H2[i] = H2[i + 1] * P + M[i]; ll wzo = Hasz(H1, p, 0, n - 1); ll il = 0; for (int i = 0; i <= m - n; ++i) if (Hasz(H2, p, i, i + n - 1) == wzo) ++il; if (MyNodeId() == 0) cout << il; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include "poszukiwania.h" #include "message.h" #include <iostream> #include <vector> using namespace std; typedef long long ll; const ll P = 90000007; ll Hasz(vector<ll>& H, vector<ll>& p, ll po, ll ko) { return H[po] - p[ko - po + 1] * H[ko + 1]; } int main() { ios_base::sync_with_stdio(0); ll n = SignalLength(); vector<ll> S(n); for (int i = 0; i < n; ++i) S[i] = SignalAt(i + 1); ll m = SeqLength(); vector<ll> M(m); for (int i = 0; i < m; ++i) M[i] = SeqAt(i + 1); ll dlo = max(n, m); vector<ll> p(dlo); p[0] = 1; for (int i = 1; i < dlo; ++i) p[i] = p[i - 1] * P; vector<ll> H1(n + 1); H1[n] = 0; for (int i = n - 1; i >= 0; --i) H1[i] = H1[i + 1] * P + S[i]; vector<ll> H2(m + 1); H2[m] = 0; for (int i = m - 1; i >= 0; --i) H2[i] = H2[i + 1] * P + M[i]; ll wzo = Hasz(H1, p, 0, n - 1); ll il = 0; for (int i = 0; i <= m - n; ++i) if (Hasz(H2, p, i, i + n - 1) == wzo) ++il; if (MyNodeId() == 0) cout << il; return 0; } |