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
#include <bits/stdc++.h>
#include <message.h>
#include <poszukiwania.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, PLL> PP;
typedef unsigned int ui;
const int mod = 1e9+7;
const int inf = 1e9+9;
const ll MOD = 1e9+696969;
const ll INF = 1e18;

int main()
{
	if (MyNodeId() == 0) {
		int n = SeqLength();
		int m = SignalLength();
		int s[n + m + 5];
		for (int i=1; i<=m; ++i) s[i] = SignalAt(i);
		s[m + 1] = -1;
		for (int i=1; i<=n; ++i) s[i + m + 1] = SeqAt(i);
		int PI[n + m + 5];
		PI[0] = PI[1] = 0;
		int dl = n + m + 1, b = 0, wyn =0;
		for (int i=2; i<=dl; ++i)
		{
			while (b > 0 && s[i] != s[b + 1]) b = PI[b];
			if (s[i] == s[b + 1]) ++b;
			PI[i] = b;
			if (PI[i] == m) ++wyn;
		}
		printf("%d", wyn);
	}
}