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
#include <vector>
#include <cstdio>
#include "message.h"
#include "poszukiwania.h"

using namespace std;

int main() {
	if(MyNodeId() == 0) {
		unsigned int s_len = SignalLength();
		unsigned int m_len = SeqLength();
		vector<unsigned int> ans;
		vector<unsigned int> T(s_len+1, -1);
		
		for(int i = 1; i <= s_len; i++)
		{
			unsigned int pos = T[i - 1];
			while(pos != -1 && SignalAt(pos+1) != SignalAt(i)) pos = T[pos];
			T[i] = pos + 1;
		}

		unsigned int sp = 0;
		unsigned int kp = 0;
		while(sp < m_len)
		{
			while(kp != -1 && (kp == s_len || SignalAt(kp+1) != SeqAt(sp+1))) kp = T[kp];
			kp++;
			sp++;
			if(kp == s_len) ans.push_back(sp - s_len);
		}
		
		printf("%lld\n", ans.size());
	}

	return 0;
}