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
#include "poszukiwania.h"
#include "message.h"
#include <iostream>
using namespace std;

#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))

long long n,m;
int counter;

bool compare (long long start)
{
	for(long long i=1;i<=m;i++)
		if (SignalAt(i) != SeqAt(i+start-1))
			return false;

	return true;
}


void KR(long long starting, long long ending) {
   long long d, hx =0, hy =0;
   long long i, j;

   for (d = i = 1; i < m; ++i)
      d = (d<<1);

   for (i = 1; i <= m; ++i) {
      hx = ((hx<<1) + SignalAt(i));
      hy = ((hy<<1) + SeqAt(i+starting-1));
   }

   j = 1;
   while (j <= ending-starting) {
      if (hx == hy && compare(j+starting-1))
         counter++;
         
      if (j != ending-starting) hy = REHASH(SeqAt(j+starting-1), SeqAt(j + starting + m- 1), hy);
      ++j;
   }
}

int main()
{
  n = SeqLength();
  m = SignalLength();


  int nodes = NumberOfNodes();
  int instance = MyNodeId();

  long long attempts = n - m + 1;
  long long amount = attempts/nodes;
  long long starting = amount*instance +1;


	if (instance<attempts%nodes)
	{
		starting+= instance;
	}
	else
	{
		starting += attempts%nodes;
	}

	long long ending = starting + amount;


	if (instance<attempts%nodes)
	{
		ending++;
	}

  counter = 0;
  if ( starting != ending) KR(starting, ending);
  
  //cout<<counter<<endl;

  if(instance != 0)
  {
	PutInt(0, counter);
	Send(0);
  }
  else
  {
	  long long counted = counter;

      
	  for(int k = 1; k<nodes; k++)
	  {
          Receive(k);
		  int received;
		  received = GetInt(k);
		  
		  //cout<<received<<endl;
		  counted += received;
	  }

	  cout<<counted<<endl;
	  return 0;
  }
}