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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "poszukiwania.h"
#include "message.h"
#include <algorithm>
#include <iostream>

int main() {
    long long node_id = MyNodeId();
    long long node_num = NumberOfNodes();

    long long n = SignalLength();
    long long M = SeqLength();

    long long poczatek = (node_id * M) / node_num;
    long long koniec = ((node_id + 1) * M) / node_num + n - 1;
    if (koniec > M)
        koniec = M;
    long long znalezione = 0;
    long long m = koniec - poczatek;
    // std::cout << node_id << ": " << poczatek << ", " << koniec << std::endl;
    // std::cout << M << " " << m << std::endl;

    long long P[m];
    P[0] = -1;
    long long t = -1;
    for (long long j = 1; j <= m; ++j) {
        while (t >= 0 && SeqAt(poczatek + t + 1) != SeqAt(poczatek + j)) t = P[t];
        ++t;
        P[j] = t;
    }


    // for (long long j = poczatek; j < koniec; ++j) {
    //     std::cout << SeqAt(j + 1) << " ";
    // }
    // std::cout << std::endl;
    // for (long long j = 0; j < n; ++j) {
    //     std::cout << SignalAt(j + 1) << " ";
    // }
    // std::cout << std::endl;
    // std::cout << "-----\n";
    // for (long long j = 0; j < m; ++j) {
    //     std::cout << P[j] << " ";
    // }
    // std::cout << std::endl;


    long long i = 0, j = 0;
    while (i <= m - n) {
        while (j < n && SignalAt(j + 1) == SeqAt(poczatek + i + j + 1)) ++j;
        if (j == n) {
            ++znalezione;
            j = 0;
            ++i;
            continue;
        }
        i += j - P[j];
        j = P[j] > 0 ? P[j] : 0;
        // j = std::max(0, P[j]);
    }

    if (MyNodeId() > 0) {
        PutLL(0, znalezione);
        Send(0);
    } else {
        for (long long i = 1; i < node_num; ++i) {
            long long instancja = Receive(-1);
            znalezione += GetLL(instancja);
        }
        std::cout << znalezione << std::endl;
    }
    return 0;
}