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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#include "message.h"
#include "poszukiwania.h"
using namespace std;
#define INF 1010000000
#define EPS 1E-12
#define MP make_pair
#define ST first
#define ND second
#define SZ(x)((int)(x).size())
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define REP(i,n) for(int i=0; i<(n); ++i)
#define REPD(i,n) for(int i=(n)-1; i>=0; --i)
#define FOR(i,a,n) for(LL i=(a); i<=(n); ++i)
#define FORD(i,a,n) for(int i=(a); i>=(n); --i)
#define FORE(i,a) for(__typeof((a).begin()) i=(a).begin();i!=(a).end();++i)
#define D(x) cerr<<#x<<" = "<<x<<", ";
#define DE(x) cerr<<#x<<" = "<<x<<endl;
#define DE2(x,y) cerr<<x<<": "<<y<<endl;
#define D2(t,a,b,n,m) {FOR(_i_, a, n){FOR(_j_, b, m)cerr<</*setw(3)*/" "<<t[_i_][_j_];cerr<<endl;}}
#define B1(w) "("<<w<<")"
#define B2(w,x) "("<<w<<","<<x<<")"
#define B3(w,x,y) "("<<w<<","<<x<<","<<y<<")"
#define B4(w,x,y,z) "("<<w<<","<<x<<","<<y<<","<<z<<")"
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
inline bool eq(double a, double b)
	{return abs(a-b)<EPS;}
template<class c1, class c2>
ostream &operator <<(ostream &out, pair<c1, c2> p)
	{return out<<"("<<p.ST<<","<<p.ND<<")";}
template<class c1>
void DB(c1 _ts_, c1 _te_)
	{while(_ts_!=_te_)cerr<</*setw(3)*/" "<<*_ts_, _ts_++;cerr<<endl;}
template<class c1>
void DB(queue<c1> _q_)
	{while(!_q_.empty())cerr<</*setw(3)*/" "<<_q_.front(), _q_.pop();cerr<<endl;}
template<class c1>
void DB(stack<c1> _s_)
	{while(!_s_.empty())cerr<</*setw(3)*/" "<<_s_.top(), _s_.pop();cerr<<endl;}


int main()
{
	LL n = SignalLength(), m = SeqLength();
	if(MyNodeId() > 0)
		return 0;
	vector<int> wz;
	
	REP(i, n)
		wz.PB(SignalAt(i + 1));
		
	wz.PB(-1);
	
	REP(i, m)
		wz.PB(SeqAt(i + 1));
	
	////
	// DB(ALL(wz));
	////
	
	vector<int> pr(SZ(wz));
	pr[0] = -1;
	int k = -1;
	int res = 0;
	
	FOR(i, 1, SZ(wz) - 1)
	{
		k = pr[i - 1];
		
		while(k >= 0 && wz[k + 1] != wz[i])
			k = pr[k];
		
		if(wz[k + 1] == wz[i])
			k++;
		pr[i] = k;
		if(k == n - 1)
			res++;
	}
	
	printf("%d\n", res);
	return 0;
}
/*

5 11 
1 2 3 2 1
2 1 2 3 2 1 2 3 2 1 2

*/