#include <iostream>
#include <algorithm>
#include "poszukiwania.h"
#include "message.h"

using namespace std;
int nodes, node;
int patternLen;
int textLen;

void slave_kmp() {
    int *pattern = new int[patternLen+2];
    int *kmp = new int[patternLen+1];
    pattern[patternLen+1]=-1;
    
    pattern[1] = SignalAt(1);
    kmp[1] = 0;
    for( int i = 2, j = 0; i <= patternLen; i++ ) {
        pattern[i] = SignalAt(i);
        
        while( j and pattern[i] != pattern[j+1] )
            j = kmp[j];
        
        if( pattern[i] == pattern[j+1] )
            j++;
            
        kmp[i] = j;
    }
    
    int countBegin = 1LL*node*(textLen-patternLen+1)/nodes+1;
    int countEnd = 1LL*(node+1)*(textLen-patternLen+1)/nodes+1;
    int runEnd = countEnd+patternLen-1;
    
    int answer = 0;
    for( int i = countBegin, j = 0; i < runEnd; i++ ) {
        int val = SeqAt(i);
        while( j and val != pattern[j+1] )
			j = kmp[j];
		if( val == pattern[j+1] )
			j++;
		if( j == patternLen )
            answer++;
    }
    PutInt(0, answer);
    Send(0);
    
    delete [] pattern;
}

void master() {
    int answer = 0;
    for( int i = 0; i < nodes; i++ ) {
        Receive(i);
        answer += GetInt(i);
    }
    cout << answer << endl;
}

int main() {
    node = MyNodeId();
    nodes = NumberOfNodes();
    patternLen = SignalLength();
    textLen = SeqLength();
    
    slave_kmp();
    if( node == 0 )
        master();
        
    return 0;
}