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
#include <bits/stdc++.h>

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

int main()
{
    int p = SignalLength();
    int n = SeqLength();

    int text[n];
    int pattern[p];

    int i, m = n+p+1, t = 0;

    for(i = 0; i < p; ++i)
        pattern[i] = SignalAt(i+1);

    for(i = 0; i < n; ++i)
        text[i] = SeqAt(i+1);

    /** MERGE **/

    int merge[m];

    merge[p] = 0;

    std::copy(pattern, pattern+p, merge);
    std::copy(text, text+n, merge+p+1);

    /** PREF **/

    int P[m];

    for(i = 1; i < m; ++i)
    {
        while(t && merge[t] != merge[i])
            t = P[t];

        if(merge[t] == merge[i])
            ++t;

        P[i] = t;
    }

    /** RESULTS **/

    int results = 0;

    for(i = p+1; i < m; ++i)
        if(P[i] == p)
            ++results;

    printf("%d", results);
}