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
119
120
121
122
#include "message.h"
#include "poszukiwania.h"
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> wzorzec;
vector<int> shifts;

int n, m;
int result = 0;

void computePrefixFunction()
{
	shifts.resize(wzorzec.size() + 1);

	shifts[1] = 0;
	int k = 0;
	for (int q = 2; q <= m; q++)
	{
		while (k > 0 && wzorzec[k] != wzorzec[q - 1])
			k = shifts[k];

		if (wzorzec[k] == wzorzec[q - 1])
			++k;
		shifts[q] = k;
	}
}

//------to remove ------
//int MyNodeId()
//{
//	return 0;
//}
//
//int NumberOfNodes()
//{
//	return 1;
//}
//
//vector<int> values;
//void PutLL(int target, long long value)
//{
//	values.push_back(value);
//}
//
//void Send(int t)
//{
//
//}
//
//int Receive(int i)
//{
//	return -1;
//}
//
//long long GetLL(int i)
//{
//	if (values.empty())
//		return 0;
//	int v = *values.rbegin();
//	values.pop_back();
//	return v;
//}

//------to remove ------

void compute()
{
	m = SignalLength();
	wzorzec.resize(m);
	for (int i = 1; i <= m; ++i)
		wzorzec[i - 1] = SignalAt(i);

	computePrefixFunction();

	n = SeqLength();

	int nodes = NumberOfNodes();
	int first = (MyNodeId() * n) / NumberOfNodes();
	int last = ((MyNodeId() + 1) * n) / NumberOfNodes() + m - 1;

	int q = 0;
	for (int i = first; i < std::min(n, last); ++i)
	{
		int value = SeqAt(i + 1);
		while (q>0 && wzorzec[q] != value)
			q = shifts[q];
		if (wzorzec[q] == value)
			q++;
		if (q == m)
		{
			++result;
			q = shifts[q];
		}
	}
}

int main()
{
	int node = MyNodeId();
	compute();
	PutLL(0, result);
	Send(0);

	if (node == 0)
	{
		int total_result = 0;
		int nodes = NumberOfNodes();
		for (int i = 0; i < nodes; ++i)
		{
			Receive(i);
			total_result += GetLL(i);
		}

		printf("%d\n", total_result);
	}

	return 0;
}