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

long long int n,m, S, count;


int main(){
    n = SignalLength();
    m = SeqLength();

    if(MyNodeId() == 0){
	long long int* KMP = new long long int[n+1];
	    KMP[0] = 0;
	    KMP[1] = 0;
	    S = 0;
	    for(long long int i = 2; i <= n; i++){
	      while((S > 0) && (SignalAt(S+1) != SignalAt(i-1+1))){
		S = KMP[S];
	      }
	      if(SignalAt(S+1) == SignalAt(i-1+1)) S++;
	      KMP[i] = S;
	    }
	    
	    long long int i = 1;
	    long long int j = 0;
	    count = 0;
	    while (i <= m-n+1){
	    	j = KMP[j];
	    	while((j < n) && (SignalAt(j+1)==SeqAt(i+j-1+1))) j++;
	    	if(j==n) {
	    		//printf("%lld\n",i);
	    		count++;
			}
			i=i+((1>j-KMP[j])?1:(j-KMP[j]));
	     }
	
    	printf("%lld\n",count);
	delete [] KMP;
    }
}