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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*	Arkadiusz Wróbel
 *
 *	Konkurs: Potyczki Algorytmiczne 2015, runda 4B
 *	Zadanie: Poszukiwania
 */

#include "poszukiwania.h"
#include "message.h"

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

#include <cstdio>
#include <iostream>

#include <algorithm>
#include <cmath>
#include <cstring>

#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<PII> VPII;
typedef vector<VI> VVI;

#define REP(I, N) for(int I = 0; I < (N); ++I)
#define FOR(I, M, N) for(int I = (M); I <= (N); ++I)
#define FORD(I, M, N) for(int I = (M); I >= (N); --I)
//#define FOREACH(IT, CON) for(__typeof((CON).begin()) IT = (CON).begin(); IT != (CON).end(); ++IT)

#define ST first
#define ND second
#define MP make_pair
#define PB push_back
#define SIZE(CON) ((int)(CON).size())
#define ALL(CON) (CON).begin(), (CON).end()

const int INF = 1000000000;
const LL INFLL = 1000000000000000000LL;

//######################################################################

int n, m;
vector<int> prefSuf;

inline int getFromS(const int v) {
	if (v == m) {
		return 2000000000;	
	}
	if (v < m) {
		return (int)SignalAt(v + 1);
	} else {
		return (int)SeqAt(v - m);
	}
}

inline void prefikso_sufiksy() {
	int v = 0;
	prefSuf[0] = 0;
	for (int i = 1; i < SIZE(prefSuf); ++i) {
		while (v > 0 && getFromS(v) != getFromS(i)) {
			v = prefSuf[v-1];
		}
		if (getFromS(v) == getFromS(i)) {
			++v;
		}
		prefSuf[i] = v;
	}
}

inline int szukanieWzorcaWTekscie() {
	prefikso_sufiksy();
	
	int wyn = 0;
	const int sup = n + m;
	FOR(i, m + 1, sup) {
		if (prefSuf[i] == m)
			++wyn;
	}
	return wyn;
}

void make() {
	n = SeqLength();
	m = SignalLength();
	prefSuf.resize(n + 1 + m);
	
	printf("%d\n", szukanieWzorcaWTekscie());
}

int main()
{
	if (MyNodeId()) {
		return 0;
	}
	make();
	return 0;
}