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
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <vector>
#include "message.h"
#include "poszukiwania.h"

#define MAX_SIZE 10000000
int prefixy[MAX_SIZE];
int prefixyIndeksy[MAX_SIZE];

typedef std::pair<long long int, long long int> LLPair;

long long int max(long long int a, long long int b){
	return a > b ? a : b;
}


void sendSpaces(long long int totalLen, long long int partLen, long long int totalNodes){
	long long int firstPos = 1;
	long long int lastPos = partLen;
	for(int i = 0; i < totalNodes - 1; i++){
		PutLL(i, firstPos);
		PutLL(i, lastPos);
		Send(i);
		firstPos = lastPos + 1;
		lastPos += partLen;
	}
	//ostatani czesc juz jest do konca
	PutLL(totalNodes - 1, firstPos);
	PutLL(totalNodes - 1, totalLen);
	Send(totalNodes - 1);
}


LLPair getSpace(){
	Receive(0);
	long long int b = GetLL(0);
	long long int e = GetLL(0);
	//printf("poczatek %lld koniec %lld\n",b,e);
	return LLPair(b,e);
}


int countPrefix(){
	long long int patterLen = SignalLength();
	int pIndex = 1;
	int prefixVal = 0;
	int step = (patterLen / MAX_SIZE) + 1;
	int prefixIndex = 1;
	prefixy[0] = -1;
	prefixyIndeksy[0] = 0;
	prefixy[1] = 0;
	prefixyIndeksy[1] = 1;
	if (step > 1) prefixIndex = 0;//omijamy punkt zerowy

	for(int i = 2; i <= patterLen; i++){
		//printf("%d %d\n", i, pIndex);
		if (SignalAt(pIndex) == SignalAt(i)){
			pIndex++;
			prefixVal++;
		} else {
			pIndex = 1;
			prefixVal = 0;
		}
		//printf("%d ===\n", prefixVal);
		if (i % step == 0) {
			prefixIndex++;
			prefixy[prefixIndex] = prefixVal;
			prefixyIndeksy[prefixIndex] = i;
		}
	}
	//prefixy[patterLen] = 0;//ostatni musi byc zerem, gdyz ten juz wystaje i nie powinien byc brany pod uwage
	//for(int i = 0; i < MAX_SIZE; i++)	printf("(%d %d) ",prefixy[i],prefixyIndeksy[i]);	printf("\n");
	return step;
}

long long int launchKmp(long long int b, long long int e, int step){
	long long int patternSize = SignalLength();
	long long int textSize = SeqLength();
	long long int posInText = b;
	long long int posPrefix = 0;
	long long int shift = 0;
	long long int found = 0;
	while(posInText <= e && posInText <= textSize - patternSize){
		//printf("shift %lld posPrefix %lld posInText %lld=================\n", shift, posPrefix, posInText);
		while(shift < patternSize && SeqAt(posInText + shift) == SignalAt(shift + 1)) shift++;
		if (shift == patternSize) {
			//printf("ZNALAZL \n");
			found++;
			//shift--;//by poprawnie sie prefiks wyliczyl
		}
		posPrefix = shift / step;
		//printf("shift %lld posPrefix %lld posInText %lld ruch %d\n", shift, posPrefix, posInText, prefixyIndeksy[posPrefix] - prefixy[posPrefix]);
		posInText = posInText + prefixyIndeksy[posPrefix] - prefixy[posPrefix];
		shift = max(0,prefixy[posPrefix]);
		//printf("AFTER SHIFT text %lld shift %lld %d %d\n",posInText,shift,(posInText <= e ),( posInText <= textSize - patternSize));
	}
	return found;
}

//./rpa_linux/executable/parunner -n=1  -stdout=tagged ~/workspace/Potyczki2015B4/Debug/Potyczki2015B4
int main(){
	int id = MyNodeId();
	int totalNodes = NumberOfNodes();


	long long int signalLen = SignalLength();
	long long int len = SeqLength() - signalLen + 1;//interesuja nas poczatki poszukiwania, wlacznie z ostatnim
	long long int partLen = len/totalNodes;
	if (id == 0){
		sendSpaces(len, partLen, totalNodes);
	}

	int step  = countPrefix();
	LLPair space = getSpace();
	long long int f = space.second == 0 ? 0 :launchKmp(space.first, space.second, step);
	//printf("%lld\n",f);
	PutLL(0, f);
	Send(0);
	if (id == 0){
		long long int total = 0;
		for(int i = 0; i < totalNodes; i++){
			Receive(i);
			total += GetLL(i);
		}
		printf("%lld\n",total);
	}
	/*
	int n = 0;
	int r = 0;
	for(int i = 0; i < 100000000; i++){
		r+=SeqAt(i % 100000);

	}*/
	return 0;
}