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
#include "poszukiwania.h"
#include "message.h"
#include <cstdio>
typedef long long int LL;

const int MAXN = 10000000;
const int SEPARATOR = 1000000001;

int p[MAXN];
int word[MAXN];

int main() {
    if (MyNodeId() != 0)
        return 0;

    int n = SeqLength();
    int m = SignalLength();
    
    for (int i = 1; i <= m; i++) 
        word[i] = SignalAt(i);
    word[m + 1] = SEPARATOR;
    for (int i = 1; i <= n; i++)
        word[m + i + 1] = SeqAt(i);

    int res = 0;
    p[0] = -1;
    for (int i = 1; i <= n + m + 1; i++) {
        int it = i - 1;
        while (p[it] >= 0 && word[p[it] + 1] != word[i])
            it = p[it];
        p[i] = p[it] + 1;
        if (p[i] == m)
            res++;
    }
    
    printf("%d\n", res);
    return 0;
}