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
73
74
75
76
77
78
79
80
#include <cstdio>
#include <algorithm>
#include "message.h"
#include "poszukiwania.h"
using namespace std;

typedef long long LL;

int match(int mess_offset, int sig_offset, LL limit) {
    // number of comparison matches until end or mismatch
    for(int i = 0; i < limit; ++i) {
        if(SignalAt(i + sig_offset + 1) != SeqAt(i + mess_offset + 1)) {
            return i;
        }
    }
    return limit;
}

int main() {
    LL siglen = SignalLength();
    LL messagelen = SeqLength();
    int positions = messagelen - siglen + 1;
    int nodes = NumberOfNodes();
    int node_id = MyNodeId();

    if(positions >= nodes || (siglen / nodes) == 0) { // many shifts, each instance calculates her shifts
        // or signals are too short to be split among instances like we do in second case
        LL results = 0;
        for(int pos = node_id; pos < positions; pos += nodes) {
            if(match(pos, 0, siglen) == siglen) {
                ++results;
            }
        }

        PutLL(0, results);
        Send(0);
        if(node_id == 0) {
            LL final_results = 0;
            for(int inst = 0; inst < nodes; ++inst) {
                Receive(inst);
                final_results += GetLL(inst);
            }
            printf("%lld\n", final_results);
        }
    } else { // few shifts, preferably long signals, instances work together on same shifts
        int work_per_inst = siglen / nodes;
        for(int pos = 0; pos < positions; ++pos) {
            int start = node_id * work_per_inst; // instance offset
            LL matched = match(start + pos, start, work_per_inst);
            if(node_id == nodes - 1) { // last one works harder
                int left = siglen - nodes * work_per_inst;
                if(matched == work_per_inst && left > 0) { // dont overdo
                    matched += match(pos + siglen - left, 0, left);
                }
            }
            PutLL(0, matched);
        }

        Send(0);
        if(node_id == 0) {
            LL final_results = 0;
            for(int inst = 0; inst < nodes; ++inst) {
                Receive(inst);
            }
            for(int pos = 0; pos < positions; ++pos) {
                LL parts = 0;
                for(int inst = 0; inst < nodes; ++inst) {
                    parts += GetLL(inst);
                }
                if(parts == siglen) {
                    ++final_results;
                }
            }

            printf("%lld\n", final_results);
        }
    }

    return 0;
}