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
//Jan Omeljaniuk
//
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <cassert>
#include <iostream>
#include <algorithm>

#define unm unsigned long long int
#define nm long long int
#define uint unsigned int

using namespace std;

#include "message.h"
#include "poszukiwania.h"
/*
vector<long long> seq = {2,1,2,3,2,1,2,3,2,1,2};
vector<long long> sig = {1,2,3,2,1};
int MyNodeId(){ return 0; }
long long SignalLength(){ return 5; }
long long SeqLength() { return 11; }
long long SignalAt(long long i) {return sig[i-1];}
long long SeqAt(long long i) {return seq[i-1];}
*/

vector<uint> p;
vector<uint> wzorzec;
vector<uint> tekst;


void pref_suf(vector<uint> &ps){
	const uint sz = SignalLength() + 1;
	ps.resize(sz);
	uint j = 0;
	for(uint i = 2; i < sz; ++i){
		while( j > 0 && SignalAt(j+1) != SignalAt(i) )
			j = ps[j];
		if( SignalAt(j+1) == SignalAt(i) )
			++j;
		ps[i] = j;
	}
}

uint kmp(vector<uint> &ps){
	uint j = 0, res=0;
	const uint wzrsz = SignalLength() + 1;
	const uint txtsz = SeqLength() + 1;
	for(uint i = 1 ; i < txtsz ; ++i ) {
		while( j > 0 && SignalAt(j+1) != SeqAt(i))
			j = ps[j];
		if(SignalAt(j+1)==SeqAt(i))
			j++;
		if(j==wzrsz-1){
			j = ps[j];
			++res;
		}
	}
	return res;
}

int main(){

	ios_base::sync_with_stdio(0);

	if(MyNodeId()==0) {
		//Single threading FTW!
		pref_suf(p);
		cout << kmp(p) << "\n";
	}

	return 0;
}