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;
}