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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include "message.h"
#if 1
#include "poszukiwania.h"
#elif 0
#include "poszukiwania-test.h"
#elif 0
#include "poszukiwania-t.h"
#endif
#include <cstdio>
using namespace std;

typedef unsigned int       u32;
typedef unsigned long long u64;
typedef signed long long   i64;

const int INF = 0x7fffffff;

#define min(a,b) (((a)<(b))?(a):(b))
#define fprintf(...)

u32 S;
u32 M;
int id;
    
int calculate(u32 b, u32 e)
{
fprintf(stderr, "[%d] calculate(b=%u, e=%u)\n", id, b, e);
    if(e > ((M+1)-S)) e = (M+1)-S;
    if(e <= b) return 0;

    int *s = new int[S];
    int *m = new int[S+(e-b)+2];
    int *sptr = s;
    int *mptr = m;
    
    for(u32 i=0; i<S ;++i) *sptr++ = SignalAt(i+1);
    for(u32 i=b; i<(e+S-1); i++) *mptr++ = SeqAt(i+1);
    
    int result = 0;
    e-=b;
    for(u32 a=0; a<e; a++)
    {
        for(u32 i=0; i<S ;++i) if(s[i]!=m[i+a]) goto _next;
        ++result;
        _next:
        ;
    }
    return result;
}
    
void master()
{
    int nodes = NumberOfNodes();
    int result = 0;
    
    u32 step = (M - S) / nodes + 1;
    fprintf(stderr, "[%d] master nodes=%d M=%u S=%u step=%u\n", id, nodes, M, S, step);
    u32 begin = 0;
    u32 end = step;

    for(int n=1; n<nodes; ++n)
    {
        PutInt(n,begin);
        PutInt(n,end);
        Send(n);
        begin+=step;
        end+=step;
    }
    fprintf(stderr, "[%d] master begin=%u end=%u (to be checked)\n", id, begin, end);
    
    end = (M+1)-S;
    fprintf(stderr, "[%d] master now end=%u\n", id, end);
    if(begin < end)
        result = calculate(begin, end);
        
    for(int n=1; n<nodes ;++n)
    {
        int id = Receive(-1);
        result += GetInt(id);
    }
    
    printf("%d\n", result);
}

void slave()
{
    Receive(0);
    u32 begin = GetInt(0);
    u32 end = GetInt(0);
    PutInt(0, calculate(begin, end));
    Send(0);
}

int main()
{
    S = SignalLength();
    M = SeqLength();

    id = MyNodeId();
    fprintf(stderr, "[%d] START\n", id);
    if(id == 0)
        master();
    else
        slave();
    fprintf(stderr, "[%d] EXIT\n", id);
    return 0;
}