#include <iostream> #include <cstdlib> #include "poszukiwania.h" #include "message.h" #include <sstream> template <class T> inline std::string to_string (const T& t) { std::stringstream ss; ss << t; return ss.str(); } using namespace std; const int SIZE = 1000000+15; const long long x = 7, y = 1000000007; long long hasze[SIZE]; int main() { ios_base::sync_with_stdio(false); long long tLen = SeqLength(); long long wLen = SignalLength(); string w = "", t = ""; for(long long i=0; i<tLen; ++i) t += to_string(SeqAt(i)); for(long long i=0; i<wLen; ++i) w += to_string(SignalAt(i)); long long haszWzorca = 0; for(long long i=w.size()-1; i>=0; --i) haszWzorca = (haszWzorca*x + w[i]) % y; hasze[t.size()] = 0; for(int i=t.size()-1; i>=0; i--) { long long a = (hasze[i+1]*x) % y; hasze[i] = (a + t[i]) % y; } long long xN=1; for(int i=1; i<=w.size(); ++i) xN = (xN * x) % y; long long out = 0; for(int i=0; i<=t.size()-w.size(); ++i) { long long a = (hasze[i+w.size()] *xN)%y; if(haszWzorca == (hasze[i] - a)%y) { out++; } } if(MyNodeId() == 0) { cout << out << endl; } 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <iostream> #include <cstdlib> #include "poszukiwania.h" #include "message.h" #include <sstream> template <class T> inline std::string to_string (const T& t) { std::stringstream ss; ss << t; return ss.str(); } using namespace std; const int SIZE = 1000000+15; const long long x = 7, y = 1000000007; long long hasze[SIZE]; int main() { ios_base::sync_with_stdio(false); long long tLen = SeqLength(); long long wLen = SignalLength(); string w = "", t = ""; for(long long i=0; i<tLen; ++i) t += to_string(SeqAt(i)); for(long long i=0; i<wLen; ++i) w += to_string(SignalAt(i)); long long haszWzorca = 0; for(long long i=w.size()-1; i>=0; --i) haszWzorca = (haszWzorca*x + w[i]) % y; hasze[t.size()] = 0; for(int i=t.size()-1; i>=0; i--) { long long a = (hasze[i+1]*x) % y; hasze[i] = (a + t[i]) % y; } long long xN=1; for(int i=1; i<=w.size(); ++i) xN = (xN * x) % y; long long out = 0; for(int i=0; i<=t.size()-w.size(); ++i) { long long a = (hasze[i+w.size()] *xN)%y; if(haszWzorca == (hasze[i] - a)%y) { out++; } } if(MyNodeId() == 0) { cout << out << endl; } return 0; } |