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
108
109
110
111
112
113
114
115
116
117
118
#include "poszukiwania.h"
#include "message.h"
#include <iostream>
#include <algorithm>

using namespace std;

const unsigned long long pp = 6364136223846793005ULL;

int N;
int M;

long long RK(unsigned long long hash, int window, int from, int to)
{
  long long res = 0;
  if (from+window>=to) return 0;

  unsigned long long sighash = 0;
  unsigned long long npp = 1;

  // init hash
  for (int i = from; i < from+window; i++)
  {
    sighash *= pp;
    if (i+1>N) return res;
    sighash += SeqAt(i+1);
    if (i>from) npp *= pp;
  }

  int i = from;
  while (i + window < to)
  {
    if (sighash==hash) res++;
    // move window
    if (i+1>N) return res;
    sighash -= npp * SeqAt(i+1);
    sighash *= pp;
    if (i+window+1>N) return res;
    sighash += SeqAt(i+window+1);
    i++;
  }

  return res;
}

int main()
{
  N = SeqLength();
  M = SignalLength();
  if (MyNodeId() == 0)
  {
    int workers = NumberOfNodes()-1;

    const int MAXSEQBUF = 20000000;
    const int MAXSIGHSH = 10000000;

    int posOrder = 0;
    int worker = 0;

    unsigned long long hash = 0;
    int end = min(MAXSIGHSH, M);

    // init hash
    for (int i = 0; i < end; i++)
    {
      hash *= pp;
      hash += SignalAt(i+1);
    }

    long long res = 0;
    int jobs = 0;
    
    while (posOrder < N)
    {
      PutLL(worker+1, hash);
      PutInt(worker+1, end);
      PutInt(worker+1, posOrder);
      posOrder += min(N-posOrder,MAXSEQBUF);
      PutInt(worker+1, posOrder);
      Send(worker+1);
      jobs++;
      worker = (worker+1)%workers;
    }

    for (int i = 1; i <= workers; i++)
    {
      PutLL(i, 0);
      Send(i);
    }

    for (int i = 0; i < jobs; i++)
    {
      res += GetLL(Receive(-1));
    }

    cout << res << endl;
  }
  else
  {
    do
    {
      Receive(0);
      unsigned long long hash = GetLL(0);
      if (0 == hash) break;
      int window = GetInt(0);
      int from = GetInt(0);
      int to = GetInt(0);

      if (from - window > 0) from -= window;

      long long res = RK(hash, window, from, to);
      PutLL(0, res);
      Send(0);
    } while (true);
  }

  return 0;
}