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

using namespace std;

int n1,n2,a,t,res;

vector<int> tab;

int tekst(const int &ile){
//	printf("ile: %d\n",ile);
	if(ile == 0)return (-1);
	else if(ile == (n1 + 1))return (-2);
	else if(ile <= n1)return SignalAt(ile);
	else return SeqAt(ile - n1 - 1);	
}

void kmp(){
	//tekst = $sig#seq	
	tab[0] = tab[1] = t = 0;
	
	for(int i = 2; i < (n1 + n2 + 2); i++){
		
		a = (t + 1);
		while(t > 0 && tekst(a) != tekst(i)){
			t = tab[t];
			a = (t + 1);	
		}
		if(tekst(a) == tekst(i))t++;
		if(i <= n1)tab[i] = t;
		if(t == n1)res++;	
	}
}

int main() {
	if(MyNodeId() == 0){
		n1 = SignalLength();
		n2 = SeqLength();
		
		tab.resize(n1 + 3);
		
		kmp();
		
		cout<<res<<endl;
		
	}
}