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
#include "message.h"
#include "poszukiwania.h"

#include <iostream>
#include <vector>

long long int pow (long long int a, long long int x)
{
    long long w = a;
    for (long long int i = 1; i < x; i++)
        w *= w;

    return w;
}

using namespace std;

int main()
{
    int ilosc_czesci = NumberOfNodes() - 1;
    int signal_length = SignalLength();
    int seq_length = SeqLength();

    if (ilosc_czesci > seq_length)
        ilosc_czesci = seq_length;

    int podstawowa_dlugosc = seq_length / ilosc_czesci;

    int my_node = MyNodeId();

    if (my_node != 0 && my_node <= ilosc_czesci)
    {
        // Pobierz wzorzec od 1 + (my_n - 1) * pods_dl
        // do += podst_dl (lub do konca, dla ostatniego)

        long long int start_przeszukiwania = 1 + (my_node - 1) * podstawowa_dlugosc;
        long long int koniec_przeszukiwania = start_przeszukiwania + podstawowa_dlugosc + signal_length - 2;

        if (koniec_przeszukiwania > seq_length)
            koniec_przeszukiwania = seq_length;

        /*vector<int> wzor(signal_length + 1);
        for (int i = 1; i <= signal_length; i++)
            wzor[i] = SignalAt(i);*/

        // Pobierz tekst od pozycji start_wzorca do (koniec - start_wzorca)
        /*vector<int> tekst(koniec_przeszukiwania - start_przeszukiwania + 2);
        for (int i = 0; i <= koniec_przeszukiwania - start_przeszukiwania; i++)
        {
            //cout << start_przeszukiwania + i << endl;
            tekst[i + 1] = SeqAt(start_przeszukiwania + i);
        }*/


        // Przetworz wzorzec na pi
        vector<int> pi(signal_length + 1);
        pi[1] = 0;
        int k = 0;

        for(int q = 2; q <= signal_length; q++)
        {
            while (k > 0 && SignalAt(k + 1) != SignalAt(q))
                k = pi[q];
            if (SignalAt(k + 1) == SignalAt(q))
                k = k + 1;
            pi[q] = k;
        }

        // Odszukaj wzorca w tekscie, zapisz pozycje jego jako: pozycja_znal - dlugosc + start_wzorca
        long long int pozycje = 0;

        int q = 0;
        for (int i = 1; i <= koniec_przeszukiwania - start_przeszukiwania + 1; i++)
        {
            while (q > 0 && SignalAt(q + 1) != SeqAt(start_przeszukiwania + i - 1))
                q = pi[q];
            if (SignalAt(q + 1) == SeqAt(start_przeszukiwania + i - 1))
                q = q + 1;
            if (q == signal_length)
            {
                pozycje += 1;
                //cout << "Znaleziono na poz. " << i - koniec_wzorca + 2 * start_wzorca << endl;
                q = pi[q];
            }
        }

        //Wyslij
        PutLL(0, pozycje);
        Send(0);
    }
    else if (my_node == 0)
    {
        // Odbierz od kazdego liste pozycji
        long long int p = 0;
        for (int i = 1; i <= ilosc_czesci; i++)
        {
            Receive(i);
            p += GetLL(i);
        }
        cout << p;
    }



    return 0;
}