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
#include<bits/stdc++.h>
#include "message.h"
#include "poszukiwania.h"
using namespace std;

//int twe[15000009];
//int tmp[15000009];

int main()
{
	int s,m,wyn=0,mp,smp,ak;
	int *twe,*tmp;
	if(MyNodeId()!=0) return 0;
	s=SignalLength();
	m=SeqLength();
												//scanf("%d%d",&s,&m);
	twe=new int[s+9];
	tmp=new int[s+9];
												//for(int i=1;i<=s;++i) scanf("%d",&twe[i]);
	tmp[0]=-1;
	for(int i=1;i<=s;++i) 
	{
		twe[i]=SignalAt(i);
		tmp[i]=tmp[i-1];
		while(tmp[i]>=0 && twe[i]!=twe[tmp[i]+1]) tmp[i]=tmp[tmp[i]];
		++tmp[i];
	}
												//for(int i=0;i<=s;++i) printf("%d ",tmp[i]); printf("\n");
	tmp[s+1]=0;
	twe[s+1]=-1;
	smp=0;
	for(int i=1;i<=m;++i)
	{
		mp=smp;
		ak=SeqAt(i);
													//scanf("%d",&ak);
		while(mp>=0 && ak!=twe[mp+1]) mp=tmp[mp];
		++mp;
													//printf("%d  %d\n",mp,twe[mp]);
		smp=mp;
		if(mp==s) ++wyn;
	}
	printf("%d",wyn);
	return 0;
}